Permutation in String

Difficulty: Medium

Problem

You are given two strings, s1 and s2. Return true if some contiguous chunk of s2 uses exactly the same letters as s1 (with the same counts), just possibly in a different order. Otherwise return false.

Example

Input: s1 = "abc", s2 = "dcbaef"
Output: true
Explanation: The chunk "cba" at positions 1–3 of s2 is a rearrangement of "abc", so the answer is true.

Brute-force approach

Check every substring of s2 with length s1. Sort each and compare with sorted s1.

Steps

  1. Sort s1 to get reference
  2. For each window of size len(s1) in s2
  3. Sort the window and compare with sorted s1
  4. If match found, return true

Time complexity: O(n * k log k) · Space complexity: O(k)

Trade-offs

  • Sorting each window takes O(k log k): we re-sort overlapping windows from scratch
  • Two permutations have the same character frequencies, we don't need to sort!
  • Can we maintain a running frequency count and just compare frequencies?

Optimal approach

Key insight: Instead of sorting, maintain character frequencies for the window. Track how many characters have matching frequencies between the window and s1. When all match, we found a permutation.

Fixed-size sliding window with frequency map comparison. Maintain a match count for O(1) comparison.

Steps

  1. Build frequency map for s1
  2. Initialize window with first len(s1) characters of s2
  3. Check if initial window matches
  4. Slide: remove left char, add right char, update match count
  5. If matches == required at any point, return true

Time complexity: O(n) · Space complexity: O(1)

Pseudocode

function checkInclusion(s1, s2):
    if len(s1) > len(s2): return false
    s1Freq = frequency map of s1
    windowFreq = {}
    
    for i from 0 to len(s2):
        windowFreq[s2[i]] += 1
        if i >= len(s1):
            // Remove leftmost char
            windowFreq[s2[i - len(s1)]] -= 1
            if windowFreq[s2[i - len(s1)]] == 0:
                delete windowFreq[s2[i - len(s1)]]
        if windowFreq == s1Freq:
            return true
    return false

Hints

  • A permutation has the same character frequencies as the original
  • Use a fixed-size sliding window of length s1
  • Compare frequency maps instead of sorting

Complexity questions

Time complexity of sort-and-compare brute force?

O(n * k log k). n-k+1 windows, each sorted in O(k log k).

Time complexity of sliding window + frequency approach?

O(n). Each character added/removed in O(1), match check is O(1).

Space complexity of the optimal approach?

O(26) = O(1). Frequency maps store at most 26 lowercase letters = constant space.

Check your understanding of Permutation in String

What makes two strings permutations of each other?

Same characters with the same frequencies. Permutations have identical character frequency distributions.

For s1='ab' and s2='eidbaooo', which substring of s2 is a permutation of s1?

'ba' at index 3. 'ba' is a rearrangement of 'ab', same characters, same frequencies.

Are 'abc' and 'bca' permutations of each other?

Yes, they have the same characters with the same frequencies. Both contain one 'a', one 'b', and one 'c'. That makes them permutations.

Related problems

Keep practising