567. Permutation in String

Hash Table Two Pointers String Sliding Window

Time: O(m+n)

Space: O(1)

Intuition

Use a sliding window of size len(s1) over s2. Maintain character frequency counts. The window is a permutation of s1 when counts match.

Algorithm

1Count frequencies of s1 characters.
2Maintain a window in s2 of the same length, tracking character counts.
3Track "matches" (characters where counts are equal).
4Slide the window: add new char, remove old char, update matches. If matches==26, found.

Example Walkthrough

Input: s1="ab", s2="eidbaooo"

1.Check windows "ei","id","db","ba","ao" — "ba" matches freq of "ab".

Output: true

Common Pitfalls

•Track a "matches" counter (number of characters with equal count) for O(1) window validity check.

567.cs

// Approach: Sliding window with a 26-element frequency array and a required-
// count variable; shrink left while all characters are matched.
// Time: O(m+n) Space: O(1)

public class Solution
{
    public bool CheckInclusion(string s1, string s2)
    {
        int[] count = new int[26];
        int required = s1.Length;

        foreach (char c in s1)
            ++count[c - 'a'];

        for (int l = 0, r = 0; r < s2.Length; ++r)
        {
            if (--count[s2[r] - 'a'] >= 0)
                --required;
            while (required == 0)
            {
                if (r - l + 1 == s1.Length)
                    return true;
                if (++count[s2[l++] - 'a'] > 0)
                    ++required;
            }
        }

        return false;
    }
}

Was this solution helpful?