• Posts

Problem 567 Permutation in String

Problem Statement

Link - Problem 567

Question

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 is 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.

Solution

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        if (s1.length() > s2.length())
            return false;

        vector<int> arr1(26, 0);
        vector<int> arr2(26, 0);

        for (int i = 0; i < s1.length(); i++) {
            arr1[s1[i] - 'a']++;
            arr2[s2[i] - 'a']++;
        }

        for (int i = 0; i < s2.length() - s1.length(); i++) {
            if (matches(arr1, arr2))
                return true;
            arr2[s2[i + s1.length()] - 'a']++;
            arr2[s2[i] - 'a']--;
        }

        return matches(arr1, arr2);
    }

    bool matches(const vector<int>& arr1, const vector<int>& arr2) {
        for (int i = 0; i < 26; i++) {
            if (arr1[i] != arr2[i])
                return false;
        }
        return true;
    }
};

Complexity Analysis

| Algorithm      | Time Complexity | Space Complexity |
| -------------- | --------------- | ---------------- |
| Sliding Window | O(n)            | O(1)             |

Explanation

Intial Thoughts

To solve this problem, we should think about how to efficiently compare all substrings of s2 with the same length as s1. We should consider using a sliding window approach to scan through s2 and compare each substring with s1. We should also think about how to quickly determine if two strings are permutations of each other, such as by using a frequency count of characters. Additionally, we should check if s1 is longer than s2, in which case we can immediately return false. Furthermore, we should consider the constraints of the problem, such as the lengths of s1 and s2, and the fact that they only contain lowercase English letters.

Intuitive Analysis

Intuitively, we can solve this problem by using a sliding window to scan through s2 and compare each substring with s1. We can use two frequency arrays to count the characters in s1 and the current substring of s2. We can then compare these two arrays to determine if the current substring is a permutation of s1. If it is, we can return true. We should also consider the edge case where s1 is longer than s2, and handle it accordingly. Moreover, we should think about how to efficiently update the frequency array for the sliding window, such as by incrementing the count for the new character and decrementing the count for the old character. We should also consider using a helper function to compare the two frequency arrays, to make the code more readable and maintainable.

1. Intuition

• The problem requires checking if a permutation of string s1 exists in string s2
• To solve this, we can use a sliding window approach to compare substrings of s2 with s1
• We need to compare the character frequencies of s1 and the current substring of s2
• Using two frequency arrays arr1 and arr2 can help us compare the character frequencies efficiently
• The key insight is to update arr2 as we slide the window through s2 to reflect the changing substring
• This approach allows us to check all possible substrings of s2 with a length equal to s1 in linear time
• By comparing the frequency arrays, we can determine if a permutation of s1 exists in s2

2. Implementation

• We initialize two frequency arrays arr1 and arr2 with 26 elements to store the character frequencies of s1 and the current substring of s2
• We populate arr1 with the character frequencies of s1 using a loop that iterates over each character in s1 and updates the corresponding index in arr1
• We use a loop to slide the window through s2 and update arr2 to reflect the changing substring, checking for a match with arr1 at each position using the matches function
• The matches function compares the two frequency arrays arr1 and arr2 and returns true if they are equal, indicating a permutation of s1 exists in the current substring of s2
• We update arr2 by incrementing the count for the new character entering the window and decrementing the count for the character leaving the window using arr2[s2[i + s1.length()] - 'a']++ and arr2[s2[i] - 'a']--
• If a match is found, we immediately return true, indicating that a permutation of s1 exists in s2
• If the loop completes without finding a match, we perform a final check using the matches function and return the result

Complexity Analysis

Time Complexity:

• The time complexity of this solution can be broken down into two parts: the initial creation of arr1 and arr2 which takes O(n) time where n is the length of s1, and the sliding window iteration over s2 which takes O(m) time where m is the length of s2. Since m > n in this scenario, the dominant operation is the sliding window iteration.
• The matches function also iterates over 26 elements, but this is a constant time operation and does not affect the overall time complexity.
• Thus, the overall time complexity is O(n + m) which simplifies to O(m) or simply O(n) in terms of the input size, where n is the length of s2.

Space Complexity:

• The space complexity of this solution is determined by the extra space used by the arr1 and arr2 vectors, each of size 26.
• This space usage does not grow with the input size, hence it is considered as constant space complexity.
• Therefore, the overall space complexity is O(1) since the space used does not change with the size of the input strings s1 and s2, regardless of the for loops and the if conditions like if (matches(arr1, arr2)) and the for loop for (int i = 0; i < s2.length() - s1.length(); i++).

Footnote

This question is rated as Medium difficulty.

Hints

Obviously, brute force will result in TLE. Think of something else.

How will you check whether one string is a permutation of another string?

One way is to sort the string and then compare. But, Is there a better way?

If one string is a permutation of another string then they must have one common metric. What is that?

Both strings must have same character frequencies, if one is permutation of another. Which data structure should be used to store frequencies?

What about hash table? An array of size 26?

Similar Questions: