567. Permutation in String

Permutation in String

Problem Description

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations are the substring of s2.

 

Example 1:

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

Example 2:

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

 

Constraints:

• 1 <= s1.length, s2.length <= 104
• s1 and s2 consist of lowercase English letters.

Idea:

• Two PointersScanning left to right with sliding window
• When all the characters from s1 are used up, we have to make sure the sliding window is exactly the length of s1

Let`s Code It!

class Solution {
private:
    bool isMatch(int a[26], int b[26]){
        for(int j=0;j<26;j++){
            if(a[j] != b[j]){
                return false;
            }
        }
        return true;
    }
    
public:
    bool checkInclusion(string s1, string s2) {
        if(s1.length() > s2.length()){
            return false;
        }
        if(s1.length() == s2.length() && s1==s2){
            return true;
        }
        
        int count1[26] = {0};
        for(int i=0;i<s1.length();i++){
            int index = s1[i] - 'a';
            count1[index]++;
        }
        
        int i=0;
        int windowSize = s1.length();
        int count2[26] = {0};
        while(i<windowSize && i<s2.length()){
            int index = s2[i] - 'a';
            count2[index]++;
            i++;
        }
        
        // check if both same thn true
        if(isMatch(count1,count2)){
            return true;
        }
        
        // travse remaing
        while(i<s2.length()){
            int newIndex = s2[i] - 'a';
            count2[newIndex]++;
            int oldIndex = s2[i-windowSize] - 'a';
            count2[oldIndex]--;
            i++;
            if(isMatch(count1,count2)){
                return true;
            }
        }
        
        
        return false;
    }
};

/*
Runtime: 3 ms, faster than 98.63% of C++ online submissions for Permutation in String.
Memory Usage: 7 MB, less than 98.08% of C++ online submissions for Permutation in String.
*/

Complexity 

Time Complexity
We are scanning the string from left to right only once, hence the time complexity will be O(n).


Space Complexity
We are using constant space for count1 and count2 array

Conclusion

That’s all folks! In this post, we solved LeetCode problem#567. Permutation in String 

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to solve leetcode questions & present the most important points to consider when improving Data structure and logic,  feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!