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. Both strings contain only lowercase letters (a to z) and have at least one letter.

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, keep 26 letter counts for the window and compare them with the 26 counts of s1. When need == have, the window is a permutation. That is a complete solution. A matches counter then removes the 26-box comparison.

Fixed-size sliding window over 26 letter counts. First compare need and have after each slide (O(26 n), which is O(n)). Then add a matches counter so a round no longer compares 26 boxes.

Steps

  1. Count the letters of s1 into need (26 boxes)
  2. Walk a window of exactly len(s1) letters over s2, keeping have (26 boxes)
  3. Each slide: add the letter that arrived, subtract the letter that left
  4. If need == have, return true (O(26 n) = O(n))
  5. Improvement: keep a matches counter of agreeing boxes and return true when matches == 26

Time complexity: O(26 n) = 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 window of length len(s1)
  • Compare frequency maps instead of sorting
  • The sum of the letters is not enough: `ad` and `bc` both add up to 5
  • When the window slides, subtract the letter that left and add the letter that arrived

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). A slide changes two boxes in O(1), and comparing 26 boxes is a constant, so O(26 n) = O(n). The matches counter makes each round cost the same however big the alphabet is.

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