567. Permutations in String

📝 Problem Details

• Title: 567. Permutations in String
• Link: https://leetcode.com/problems/permutation-in-string/
• Difficulty: Medium
• Tags/Categories: Strings

input strings s1 and s2 return true if s2 contains a permutation of s1 return false otherwise

💭What Were My Initial Thoughts?

- sliding window + frequency count approach:
	- maintain a fixed size sliding window of s1.size() in s2
	- compare the frequency counts of characters in the window with s1
	- if the counts match, return true

💡 Explanation of Solution

1. base case:
	- if s1.size() > s2.size(), return false since s1 cannot fit in s2

2. use frequency arrays
	- create two frequency arrays
		- s1Freq --> size 26 
		- windowFreq --> size 26
	- populate s1Freq with character frequencies from s1
	- populate windowFreq with the first s1.size() characters in s2

3. slide window across s2
	- if s1Freq == windowFreq, return true (permutation found)
	- move the window forward:
		- include s2[i] (new character)
		- remove s2[i - s1.size()] (old character)
	- repeat until s2 is fully traversed

4. final check, if no match was found return false 

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        if(s1.size() > s2.size()) return false;
 
        vector<int> s1Freq(26,0), windowFreq(26,0);
 
        for(int i = 0; i < s1.size(); i++) {
            s1Freq[s1[i]-'a'] ++;
            windowFreq[s2[i] - 'a'] ++;
        }
 
        for(int i = s1.size(); i < s2.size(); i++) {
            if(s1Freq == windowFreq) return true;
 
            windowFreq[s2[i] - 'a']++;
            windowFreq[s2[i- s1.size()] - 'a']--;
        }
 
        return s1Freq == windowFreq;
    }
};