LeetCode: Permutation in String

Problem Statement

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:

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

Solution Thought Process

As we have to find a permutation of string s1 , let's say that the length of s1 is k. We can say that we have to check every k length subarray starting from 0. Let's say that length of s2 is L.

Let's store all the frequencies in an int remainingFrequency[26]={0}. Whenever we found an element we decrease it's remaining frequency.

The algorithm boils down to these step:

• Check [0,k-1] - this k length window, check if all the entries in the remaining frequency is 0

• Check [1,k] - this k length window, check if all the entries in the remaining frequency is 0

• Check [2,k+1] - this k length window, check if all the entries in the remaining frequency is 0

.............................................................

.............................................................

• Check [windowStart+k-1,L-1] - this k length window, check if all the entries in the remaining frequency is 0

If the frequencies are 0, then we can say that the permutation exists. For each window we have to consider the 26 values to determine if the window is an permutation.

So one thing we get hunch from here, this can be easily done in O(n) instead on any quadric time complexity.

Why?

When rolling over the next window, we can remove the left most element, and just add one right side element and change the remaining frequencies. This is called the sliding window technique.

Solution

class Solution {
private:
    int remainingFrequency[26]={0};
    bool checkFrequency(int *frequency)
    {
        for(int i=0;i<26;i++)
        {
            if(frequency[i]!=0)
            {
                return false;
            }
        }
        return true;
    }
public:
    bool checkInclusion(string s1, string s2) {
        int k=s1.size();
        for(int i=0;i<k;i++)
        {
            remainingFrequency[s1[i]-'a']++;
        }
        int windowStart=0;
        for(int windowEnd=0;windowStart+k-1<s2.size();windowEnd++)
        {
            remainingFrequency[s2[windowEnd]-'a']--;
            if(windowEnd>=k-1)
            {
                if(checkFrequency(remainingFrequency))
                {
                    return true;
                }
                remainingFrequency[s2[windowStart]-'a']++;
                windowStart++;
            }
        }
        return false;
    }
};

Complexity

Time Complexity: O(n)

Space Complexity: O(1)