Permutation in String medium

Problem Statement

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

In other words, return true if and only if some permutation of s1 is a substring of s2.

Example 1:

Input: s1 = "ab", s2 = "eidbaooo" Output: true Explanation: s2 contains the permutation "ab" of s1.

Example 2:

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

Steps:

1. Character Count: Create a map (or array if characters are ASCII) to store the frequency of each character in s1.
2. Sliding Window: Use a sliding window of size equal to the length of s1 to traverse s2.
3. Frequency Comparison: For each window in s2, count the character frequencies within the window. Compare this frequency count to the frequency count of s1. If they match, a permutation is found.
4. Sliding: Slide the window one position to the right, updating the frequency count accordingly (subtract the outgoing character, add the incoming character).
5. Return: Return true if a permutation is found; otherwise, return false after the window has traversed the entire s2.

Explanation:

The core idea is to efficiently check if a sliding window within s2 contains the same character frequencies as s1. Using a map avoids nested loops for frequency comparison, leading to a linear time solution. The sliding window technique allows for efficient traversal and updating of character counts without recomputing from scratch for each window position.

Code (C++):

#include <iostream>
#include <string>
#include <map>

using namespace std;

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

    map<char, int> s1_freq;
    for (char c : s1) {
        s1_freq[c]++;
    }

    map<char, int> window_freq;
    int window_start = 0;
    int matched = 0;

    for (int window_end = 0; window_end < s2.length(); window_end++) {
        char right_char = s2[window_end];
        window_freq[right_char]++;
        if (s1_freq.count(right_char) && window_freq[right_char] == s1_freq[right_char]) {
            matched++;
        }

        if (window_end - window_start + 1 == s1.length()) {
            if (matched == s1_freq.size()) return true;

            char left_char = s2[window_start];
            window_freq[left_char]--;
            if (s1_freq.count(left_char) && window_freq[left_char] < s1_freq[left_char]) {
                matched--;
            }
            window_start++;
        }
    }
    return false;
}

int main() {
    string s1 = "ab";
    string s2 = "eidbaooo";
    cout << checkInclusion(s1, s2) << endl; // Output: true

    s1 = "ab";
    s2 = "eidboaoo";
    cout << checkInclusion(s1, s2) << endl; // Output: false

    return 0;
}

Complexity:

• Time Complexity: O(m + n), where n is the length of s2 and m is the length of s1. We iterate through s2 once. Character frequency counting is done in O(m) and O(n) respectively.
• Space Complexity: O(1). The map stores at most 26 characters (for lowercase English letters), so the space used is constant. If the character set is larger, the space complexity becomes O(k), where k is the size of the character set.