Permutation in String - Algorithm Visualization

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

Example:

Input: s1 = "ab", s2 = "eidbaooo" → Output: true (s2 contains "ba" which is a permutation of "ab")
Input: s1 = "ab", s2 = "eidboaoo" → Output: false

Configuration

String s1 (pattern to find):

String s2 (search in):

Speed (ms): 800

Strings Visualization

s1 (pattern):

s2 (text) with sliding window:

Click Initialize to start

Frequency Comparison

s1_count

window

Matches: 0 / 0

Code

fun checkInclusion(s1: String, s2: String): Boolean {
    if (s1.length > s2.length) {
        return false
    }
    val s1Count = mutableMapOf<Char, Int>()
    val window = mutableMapOf<Char, Int>()
    for (c in s1) s1Count[c] = (s1Count[c] ?: 0) + 1
    for (i in 0 until s1.length) window[s2[i]] = (window[s2[i]] ?: 0) + 1
    if (s1Count == window) return true
    
    for (i in s1.length until s2.length) {
        window[s2[i]] = (window[s2[i]] ?: 0) + 1
        val leftChar = s2[i - s1.length]
        window[leftChar] = window[leftChar]!! - 1
        if (window[leftChar] == 0) {
            window.remove(leftChar)
        }
        if (s1Count == window) return true
    }
    
    return false

Execution Log

How It Works

Key Insight

Two strings are permutations of each other if and only if they have the same character frequencies. Instead of generating all permutations of s1 (which would be factorial time complexity), we can use a sliding window of size len(s1) on s2 and compare character frequencies at each position.

Algorithm Steps

Initial Check: If s1 is longer than s2, no permutation can exist as a substring.
Build Frequency Maps: Create a frequency map for s1 and for the first window of s2 (size = len(s1)).
Initial Comparison: If the frequencies match, we found a permutation at the start.
Slide the Window: For each subsequent position:
- Add the new character entering the window on the right
- Remove the character leaving the window on the left
- Compare the updated window frequencies with s1 frequencies
- If they match, we found a permutation
Return Result: Return true if any window matched, false otherwise.

Complexity Analysis

Time Complexity

O(n) where n is the length of s2. We iterate through s2 once, and each character frequency comparison is O(1) on average with hash maps.

Space Complexity

O(1) because the frequency maps contain at most 26 characters (lowercase English letters), which is constant space.

Why This Approach Works

The sliding window technique is perfect for this problem because:

We need to check all substrings of s2 that have the same length as s1
Instead of recalculating frequencies from scratch for each substring, we maintain a running window and update it incrementally
Comparing character frequencies is equivalent to checking if strings are permutations of each other
This reduces the time complexity from O(n × m) (where we'd check each substring independently) to O(n)