Day 17;LeetCode 30 Day may challenges

Permutation_in_a_string.cpp

class Solution {
public:
    bool check_anagrams(vector<int>& a,vector<int>& b){
        if(a == b)
            return true;
        else
            return false;
    }
    bool solve(string&s ,string& p){
        int m = p.size();
        int n = s.size();
        //inorder to be a subsring,s1.length() <= s2.length().i.e n>=m
        if(m > n){
            return false;
        }
        int flag = 0;
        vector<int> countS(26,0);
        vector<int> countP(26,0);
        for(int i=0; i<m; i++){
            countS[s[i]-'a']++;
            countP[p[i]-'a']++;
        }
        for(int i=m; i<n; i++){
            if(check_anagrams(countS,countP)){
                flag = 1;
                break;
            }
            //adding right character to make size of anagram(moving right pointer)
            countS[s[i]-'a']++;
            //removing previos leftmost character
            countS[s[i-m]-'a']--;
        }
        if(flag)
            return true;
        //after adding rightmost character
        if(check_anagrams(countS,countP)){
            return true;
        }
        return false;
    }
    bool checkInclusion(string s1, string s2) {
        return solve(s2,s1);
    }
};
/*
    bool compare(vector<int>& a,vector<int>& b){
        if(a == b)
            return true;
        else
            return false;
    }
    bool solve(string&s ,string& p){
        int m = p.size();
        int n = s.size();
        
        if(m > n){
            return false;
        }
        int flag = 0;
        //(a-z) = (97,122);(A-Z)=(65-90)
        vector<int> countS(256,0);//character ascii_values array
        vector<int> countP(256,0);
        for(int i=0; i<m; i++){
            countS[s[i]]++;
            countP[p[i]]++;
        }
        for(int i=m; i<n; i++){
            if(compare(countS,countP)){
                flag = 1;
                break;
            }
            //adding right character to make size of anagram(moving right pointer)
            countS[s[i]]++;
            //removing previos leftmost character
            countS[s[i-m]]--;
        }
        if(flag)
            return true;
        //after adding rightmost character
        if(compare(countS,countP)){
            return true;
        }
        return false;
    }
    bool checkInclusion(string s1, string s2) {
        //remember  anagram is of size p.length()
        return solve(s2,s1);
    }
*/

Problem_statement17.txt

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:

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

Input:s1= "ab" s2 = "eidboaoo"
Output: False
 

Note:

The input strings only contain lower case letters.
The length of both given strings is in range [1, 10,000].

HINTS:
   Hide Hint #1
Obviously, brute force will result in TLE. Think of something else.
   Hide Hint #2  
How will you check whether one string is a permutation of another string?
   Hide Hint #3  
One way is to sort the string and then compare. But, Is there a better way?
   Hide Hint #4  
If one string is a permutation of another string then they must one common metric. What is that?
   Hide Hint #5  
Both strings must have same character frequencies, if one is permutation of another. Which data structure should be used to store frequencies?
   Hide Hint #6  
What about hash table? An array of size 26?