Wrong Answer : Permutation in String : fix error(Leetcode)

Question

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

Example 1: (Test Case Passed)

Input: s1 = "ab" s2 = "eidbaooo"
Output: True
Explanation: s2 contains one permutation of s1 ("ba").

Example 2: (Test Case Failed)

Input: s1 = "adc", s2 = "dcda"
Output: True
Expected : False

The problem is available on leetcode : https://leetcode.com/problems/permutation-in-string/submissions/

I have passed 78/103 test cases. I am doing some mistake with using the conditions I guess, can anyone fix it.

Here's my code :

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int k = s1.length();
        HashMap<Character, Integer> map = new HashMap<>();
        for(int i=0; i<k; i++){
            char rightChar = s1.charAt(i);
            map.put(rightChar, map.getOrDefault(rightChar,0)+1);
        }
        int windowStart=0;
        int decrement=0;
        HashMap<Character, Integer> resMap = new HashMap<>();
        for(int windowEnd=0; windowEnd<s2.length(); windowEnd++){
            char nextChar = s2.charAt(windowEnd);
           resMap.put(nextChar, resMap.getOrDefault(nextChar,0)+1);
            
            if(windowEnd-windowStart+1 >= k){
                if(resMap.equals(map)){
                    return true;
                }else{         
                    char leftChar = s2.charAt(windowStart);
                     resMap.remove(leftChar);  
                     windowStart++;
                }
            }
        }
        
        return false;
    }
}

Thanks in advance :)

Answer 1

I think in your case the Time limit is exceeding. Please confirm the same. You can try the solution using Array provided by Leetcode-

public boolean checkInclusion(String s1, String s2) {

    if (s1.length() > s2.length())
        return false;
    int[] s1map = new int[26];
    for (int i = 0; i < s1.length(); i++)
        s1map[s1.charAt(i) - 'a']++;
    for (int i = 0; i <= s2.length() - s1.length(); i++) {
        int[] s2map = new int[26];
        for (int j = 0; j < s1.length(); j++) {
            s2map[s2.charAt(i + j) - 'a']++;
        }
        if (matches(s1map, s2map))
            return true;
    }
    return false;
}


public boolean matches(int[] s1map, int[] s2map) {
    for (int i = 0; i < 26; i++) {
        if (s1map[i] != s2map[i])
            return false;
    }
    return true;
}

Answer 2

There is an algorithm issue, which gives wrong answer (not an efficiency issue). This'd also pass just fine:

public class Solution {
    public final boolean checkInclusion(
        final String a,
        final String b
    ) {
        if (a.length() > b.length()) {
            return false;
        }

        int[] countmap = new int[26];

        for (int index = 0; index < a.length(); index++) {
            countmap[a.charAt(index) - 'a']++;
            countmap[b.charAt(index) - 'a']--;
        }

        if (isAllZero(countmap)) {
            return true;
        }

        for (int index = a.length(); index < b.length(); index++) {
            countmap[b.charAt(index) - 'a']--;
            countmap[b.charAt(index - a.length()) - 'a']++;

            if (isAllZero(countmap)) {
                return true;
            }
        }

        return false;
    }

    private static final boolean isAllZero(
        final int[] counts
    ) {
        for (int alphabet = 0; alphabet < 26; alphabet++)
            if (counts[alphabet] != 0) {
                return false;
            }

        return true;
    }

}

---

References

• For additional details, please see the Discussion Board where you can find plenty of well-explained accepted solutions with a variety of languages including low-complexity algorithms and asymptotic runtime/memory analysis^{1, 2}.