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 one of the anagrams of s1 is a 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

Steps:

1. Frequency Check: The core idea is to check if a sliding window of size s1.Length within s2 contains the same character frequencies as s1.

2. Sliding Window: We use a sliding window of length s1.Length to traverse s2.

3. Frequency Maps: We'll use dictionaries (or hashmaps) to store the character frequencies of s1 and the current window in s2.

4. Comparison: In each iteration, we compare the frequency maps. If they are identical, we found a permutation.

5. Sliding: We slide the window one character at a time, updating the frequency map accordingly.

Explanation:

The solution uses a sliding window approach. It maintains a frequency count of characters within the window. If the frequency count matches that of s1, a permutation is found. The window slides through s2, updating the frequencies as it moves.

Code:

using System;
using System.Collections.Generic;

public class Solution {
    public bool CheckInclusion(string s1, string s2) {
        if (s1.Length > s2.Length) return false; // Optimization: s1 can't be a permutation if it's longer than s2

        Dictionary<char, int> s1Freq = new Dictionary<char, int>();
        Dictionary<char, int> windowFreq = new Dictionary<char, int>();

        // Populate frequency map for s1
        foreach (char c in s1) {
            s1Freq[c] = s1Freq.ContainsKey(c) ? s1Freq[c] + 1 : 1;
        }

        int windowStart = 0;
        int windowEnd = 0;

        while (windowEnd < s2.Length) {
            char rightChar = s2[windowEnd];
            windowFreq[rightChar] = windowFreq.ContainsKey(rightChar) ? windowFreq[rightChar] + 1 : 1;

            //If window size is equal to s1 size, compare frequencies
            if (windowEnd - windowStart + 1 == s1.Length) {
                if (s1Freq.Equals(windowFreq)) return true;

                // Slide the window
                char leftChar = s2[windowStart];
                windowFreq[leftChar]--;
                if (windowFreq[leftChar] == 0) windowFreq.Remove(leftChar);
                windowStart++;
            }
            windowEnd++;
        }
        return false;
    }
}

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. The frequency map operations are O(1) on average.

• Space Complexity: O(1). The frequency maps use constant space because the number of unique characters in the English alphabet is fixed (or limited by the character set).