Permutation in String

Solution: Using Sliding Window

Step 0

This is our initial setup.

Step 1

Let's create a frequencyMap from pattern.

Step 2

Now, we will start iterating the given string and every time we find a matching character present in frequencyMap, we will reduce the frequency count in the frequencyMap. And if at any point in time, the frequency of the character becomes 0, we will increment matched. Here, matched will be incremented only when we find all the occurrences of the character.

Here, as you can see frequencyMap['d'] = 0 means we have found all the occurrences of 'd' in our current window. Hence, incremented matched.

Step 3

Now, 'c' does not exist in the frequencyMap. So, we will simply expand our window until we cover at least pattern sized length window.

Step 4

Here 'a' exists in frequencyMap, so we will decrement it's frequency by 1 in frequencyMap.

Step 5

Again, we have encountered 'a', so decrement it's frequency by 1 in frequencyMap. And here at this point, frequencyMap['a'] = 0, which means we have found all the occurrences of 'a' in the current window.

As we can see, we have now covered at least the pattern sized window which is 4. But matched is still not equal frequencyMap.size().

Now, current window is invalid. Hence, we will try to shrink it.

Step 6

Because 'd' is going out of the window, we would need to increment the frequency of 'd' in our frequencyMap. But before incrementing its frequency, it's important to check if frequencyMap['d'] was previously 0. If yes, we need to decrement matched first. This is because we will no more have all the occurrences of 'd' in the current window. Remember, we incremented matched when d's frequency became 0. So, we are reversing the process now.

Step 7

Current character is 'a', simply decrement it's frequency. Negative value simply tells us that we have more number of occurrences of 'a' in our current window than what we need.

Still, matched is not equal to frequencyMap.size(). Shrink the window.

Step 8

'c' will be moved out of the window.

Step 9

Current character is 'a', simply decrement it's frequency. Again negative value simply tells us that we have more number of occurrences of 'a' in our current window than what we need.

Still, matched is not equal to frequencyMap.size(). Shrink the window.

Step 10

'a' will be moved out of the window. And frequency will be incremented in frequencyMap.

Step 11

Current character is 'd', decrement its frequency and because frequency of 'd' has become 0, increment the matched because we have covered all the occurrences of 'd' in our current window.

Still, matched is not equal to frequencyMap.size(). Shrink the window.

Step 12

'a' will be moved out of the window. And frequency will be incremented in frequencyMap.

Step 13

Current character is 'p', decrement its frequency and because frequency of 'p' has become 0, increment the matched because we have covered all the occurrences of 'p' in our current window.

Now, matched is equal to frequencyMap.size(). Hence, return true immediately because we have found the permutation of the given pattern in the given string as a substring.

Let's code it now.

Java Code

class Solution {
    public boolean checkInclusion(String pattern, String string) {
        
        Map<Character, Integer> frequencyMap = new HashMap<>();
        for(char ch : pattern.toCharArray()) {
            frequencyMap.put(ch, frequencyMap.getOrDefault(ch, 0) + 1);
        }

        int matchedCount = 0;
        int windowStart = 0;
        
        for(int windowEnd = 0; windowEnd < string.length(); windowEnd++) {
            char currChar = string.charAt(windowEnd);
            if(frequencyMap.containsKey(currChar)) {
                frequencyMap.put(currChar, frequencyMap.get(currChar) - 1);
                if(frequencyMap.get(currChar) == 0) {
                    matchedCount += 1;
                }
            }

            if(matchedCount == frequencyMap.size()) return true;

            if(windowEnd >= pattern.length() - 1) {
                char leftChar = string.charAt(windowStart);
                windowStart += 1;
                if(frequencyMap.containsKey(leftChar)) {
                    if(frequencyMap.get(leftChar) == 0) {
                        matchedCount -= 1;
                    }
                    frequencyMap.put(leftChar, frequencyMap.get(leftChar) + 1);
                }
            }
        }
        return false;
    }
}

C++ Code

class Solution {
public:
    bool checkInclusion(string pattern, string str) {
        unordered_map<char, int> frequencyMap;
        for(char ch : pattern) {
            frequencyMap[ch] += 1;
        }

        int matchedCount = 0;
        int windowStart = 0;
        
        for(int windowEnd = 0; windowEnd < str.size(); windowEnd++) {
            char currChar = str[windowEnd];
            if(frequencyMap.find(currChar) != frequencyMap.end()) {
                frequencyMap[currChar] -= 1;
                if(frequencyMap[currChar] == 0) {
                    matchedCount += 1;
                }
            }

            if(matchedCount == frequencyMap.size()) return true;

            if(windowEnd >= pattern.size() - 1) {
                char leftChar = str[windowStart];
                windowStart += 1;
                if(frequencyMap.find(leftChar) != frequencyMap.end()) {
                    if(frequencyMap[leftChar] == 0) {
                        matchedCount -= 1;
                    }
                    frequencyMap[leftChar] += 1;
                }
            }
        }
        return false;
    }
};

Python Code

class Solution:
    def checkInclusion(self, pattern: str, string: str) -> bool:
        frequency_map = dict()
        for ch in pattern:
            frequency_map[ch] = frequency_map.get(ch, 0) + 1

        matched_count = 0
        window_start = 0
        
        for window_end in range(len(string)):
            curr_char = string[window_end]
            if curr_char in frequency_map:
                frequency_map[curr_char] -= 1
                if frequency_map[curr_char] == 0:
                    matched_count += 1

            if matched_count == len(frequency_map): 
                return True

            if window_end >= len(pattern) - 1:
                left_char = string[window_start]
                window_start += 1
                if left_char in frequency_map:
                    if frequency_map[left_char] == 0:
                        matched_count -= 1
                    frequency_map[left_char] += 1
        return False

Complexity Analysis

Time Complexity: The time complexity of the solution is O(n), where n is the length of the input string because we iterate over the input string only once.

Space Complexity: The space complexity of the solution is O(1), since we will be storing the frequency of 26 characters at most in the hash map for the given pattern string.