10.12 Permutation in String

10.12.1 Problem Metadata

10.12.2 Description

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 s1’s permutations is a substring of s2.

10.12.3 Examples

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

10.12.4 Constraints

  • \(1 \le\) s1.length, s2.length \(\le\) \(10^4\)
  • s1 and s2 consist of lowercase English letters

10.12.5 Solution 1 - Brute Force with Frequency Map

10.12.5.1 Walkthrough

This solution uses a brute force approach that checks every possible window in s2 where a character from s1 appears. The key insight is that two strings are permutations if they have identical character frequency distributions.

Algorithm: 1. Iterate through s2 with pointer l 2. When we find a character that exists in s1, extract a substring of length s1.length() starting from that position 3. Build frequency maps for both s1 and the substring 4. Compare the frequency maps - if they match, we found a permutation

Optimization attempt: The code tries to skip characters not in s1 using s1.contains(c), but this check itself is O(m) where m is the length of s1, making the optimization ineffective.

Visual Example with s1 = "ab", s2 = "eidbaooo":

s1 = "ab", len = 2

l=0: s2[0]='e'
  s1.contains('e')? → false, skip

l=1: s2[1]='i'
  s1.contains('i')? → false, skip

l=2: s2[2]='d'
  s1.contains('d')? → false, skip

l=3: s2[3]='b'
  s1.contains('b')? → true ✓
  substring = s2[3:5] = "ba"
  freq1 = [1,1,0,...] (a=1, b=1)
  freq2 = [1,1,0,...] (a=1, b=1)
  Arrays.equals(freq1, freq2) → true ✓

Return true

Issue with this approach: The s1.contains() check is O(m) per character, and we still check every position, so the skip optimization doesn’t actually save time asymptotically.

10.12.5.2 Analysis

  • Time Complexity: O(n × m)
    • Outer loop: O(n) where n is length of s2
    • For each iteration:
      • s1.contains(c): O(m) where m is length of s1
      • buildFreqArray(s1): O(m)
      • buildFreqArray(substring): O(m)
      • Arrays.equals(): O(26) = O(1)
    • Total: O(n) × O(m) = O(n × m)
  • Space Complexity: O(1)
    • Two fixed-size frequency arrays of length 26
    • Substring creation doesn’t count as it’s temporary

Drawbacks: - Rebuilds frequency map for s1 on every check (inefficient) - The contains() check doesn’t actually skip enough work to improve complexity - Creates new substring and frequency arrays for each potential match

10.12.5.3 Implementation Steps

  1. Initialize pointer l = 0 to scan through s2
  2. For each position l:
    • Check if s2.charAt(l) exists in s1 using contains()
    • If yes, extract substring s2.substring(l, l + s1.length())
    • Build frequency arrays for both s1 and the substring
    • Compare using Arrays.equals() - if match, return true
    • Move l forward
  3. If no match found after scanning all positions, return false
  4. Helper method buildFreqArray(String s):
    • Create frequency array of size 26
    • For each character in string, increment freq[c - 'a']
    • Return the frequency array

10.12.5.4 Code - Java

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int l = 0, r = 0;
        int len = s1.length();

        while(l < s2.length()) {
            char c = s2.charAt(l);
            if(s1.contains("" + c)) {
                r = l + len;
                if(r <= s2.length() && isPermutation(s1, s2.substring(l, r))) {
                    return true;
                }

                l++;
            } else {
                l++;
            }
        }

        return false;
    }

    private boolean isPermutation(String s1, String s2) {
        if(s1.length() != s2.length()) {
            return false;
        }

        int[] freq1 = buildFreqArray(s1);
        int[] freq2 = buildFreqArray(s2);

        return Arrays.equals(freq1, freq2);
    }

    private int[] buildFreqArray(String s) {
        int[] freq = new int[26];

        for(char c: s.toCharArray()) {
            freq[c - 'a']++;
        }

        return freq;
    }
}

10.12.6 Solution 2 - Sliding Window with Frequency Map

10.12.6.1 Walkthrough

This solution optimizes the brute force approach by using a sliding window technique. Instead of rebuilding the frequency map for each window, we maintain a single frequency map and update it incrementally as the window slides.

Core Optimization: - Brute force: Creates new frequency map for each of n windows → n × m operations - Sliding window: Updates existing frequency map with 2 operations per window → 2n operations

Algorithm: 1. Build frequency map for s1 (only once) 2. Build frequency map for the first window of s2 (size = s1.length()) 3. Check if first window matches 4. Slide the window: for each subsequent position - Add the new character entering on the right - Remove the old character leaving on the left - Compare frequency maps

Visual Example with s1 = "ab", s2 = "eidbaooo":

s1 = "ab" → freq1 = [1,1,0,0,...,0] (a=1, b=1)

Step 1: Initialize first window [0:2) = "ei"
  freq2 = [0,0,0,0,1,0,0,0,1,...,0] (e=1, i=1)
  Arrays.equals(freq1, freq2) → false

Step 2: Slide to i=2, window [1:3) = "id"
  Remove s2[0]='e': freq2[4]-- → freq2 = [0,0,0,0,0,0,0,0,1,...,0]
  Add s2[2]='d':    freq2[3]++ → freq2 = [0,0,0,1,0,0,0,0,1,...,0]
  Arrays.equals(freq1, freq2) → false

Step 3: Slide to i=3, window [2:4) = "db"
  Remove s2[1]='i': freq2[8]-- → freq2 = [0,0,0,1,0,0,0,0,0,...,0]
  Add s2[3]='b':    freq2[1]++ → freq2 = [0,1,0,1,0,0,0,0,0,...,0]
  Arrays.equals(freq1, freq2) → false

Step 4: Slide to i=4, window [3:5) = "ba"
  Remove s2[2]='d': freq2[3]-- → freq2 = [0,1,0,0,0,0,0,0,0,...,0]
  Add s2[4]='a':    freq2[0]++ → freq2 = [1,1,0,0,0,0,0,0,0,...,0]
  Arrays.equals(freq1, freq2) → true ✓

Return true

Why This is Faster: - Only builds s1 frequency map once (not n times) - Updates window frequency map with 2 operations per slide instead of rebuilding - No substring creation overhead

10.12.6.2 Analysis

  • Time Complexity: O(n + m)
    • Building frequency map for s1: O(m)
    • Building frequency map for first window: O(m)
    • Sliding the window: O(n - m) iterations, each with:
      • Two frequency updates: O(1)
      • Array comparison: O(26) = O(1)
    • Total: O(m) + O(m) + O(n - m) = O(n + m), simplified to O(n) when n \(\ge\) m
  • Space Complexity: O(1)
    • Two fixed-size frequency arrays of length 26
    • No substring creation

Advantages over Solution 1: - Builds s1 frequency map only once - No substring allocation overhead - Constant-time window updates instead of O(m) rebuilds - Significantly faster for large inputs

10.12.6.3 Implementation Steps

  1. Edge case check: If s2.length() < s1.length(), return false immediately
  2. Build initial frequency maps:
    • Build freq1 for entire s1 string
    • Build freq2 for first window of s2 (substring from 0 to len)
  3. Check first window: If Arrays.equals(freq1, freq2), return true
  4. Slide the window: For i from len to s2.length() - 1:
    • Get old character leaving window: oldC = s2.charAt(i - len)
    • Get new character entering window: newC = s2.charAt(i)
    • Update frequencies: freq2[oldC - 'a']-- and freq2[newC - 'a']++
    • If frequency maps match, return true
  5. No match found: Return false
  6. Helper method buildFreqArray(String s):
    • Create frequency array of size 26
    • Iterate through string and increment freq[c - 'a'] for each character
    • Return the frequency array

10.12.6.4 Code - Java

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int len = s1.length();

        if(s2.length() < len) {
            return false;
        }

        int[] freq1 = buildFreqArray(s1);
        int[] freq2 = buildFreqArray(s2.substring(0, len));

        // Check initial window
        if(Arrays.equals(freq1, freq2)) {
            return true;
        }

        // Slide the window
        for(int i = len; i < s2.length(); i++) {
            char oldC = s2.charAt(i - len);
            char newC = s2.charAt(i);
            freq2[oldC - 'a']--;
            freq2[newC - 'a']++;

            if(Arrays.equals(freq1, freq2)) {
                return true;
            }
        }

        return false;
    }

    private int[] buildFreqArray(String s) {
        int[] freq = new int[26];

        for(char c: s.toCharArray()) {
            freq[c - 'a']++;
        }

        return freq;
    }
}

10.12.6.5 Code - Go

import "slices"

func checkInclusion(s1 string, s2 string) bool {
    len1 := len(s1)
    len2 := len(s2)

    if len2 < len1 {
        return false
    }

    freq1 := buildFreqArray(s1)
    freq2 := buildFreqArray(s2[0:len1])

    // Check initial window
    if slices.Equal(freq1, freq2) {
        return true
    }

    // Slide the window
    for i := len1; i < len2; i++ {
        oldC := s2[i-len1]
        newC := s2[i]
        freq2[oldC-'a']--
        freq2[newC-'a']++

        if slices.Equal(freq1, freq2) {
            return true
        }
    }

    return false
}

func buildFreqArray(s string) []int {
    freq := make([]int, 26)

    for _, c := range s {
        freq[c-'a']++
    }

    return freq
}

10.12.7 Solution Comparison

Aspect Solution 1 (Brute Force) Solution 2 (Sliding Window)
Time Complexity O(n × m) O(n + m)
Space Complexity O(1) O(1)
Frequency map builds n times for s1, n times for substrings 1 time for s1, 1 time for first window
Substring creation Yes (creates n substrings) Yes (only 1 for initial window)
Window updates Rebuild entire frequency map 2 array operations
Best for Small strings or learning Production code, large inputs
Code complexity Slightly more complex (contains check) Clean and efficient

Key Takeaway: Solution 2 is significantly faster because it: 1. Builds s1 frequency map only once 2. Updates the window incrementally (O(1)) instead of rebuilding (O(m)) 3. Avoids repeated substring allocations

For the given constraints (\(10^4\) characters), Solution 2 can be 100x faster than Solution 1 in worst-case scenarios.