Permutation in String

Problem

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

Examples

The brute-force approach

For every substring of s2 with the same length as s1, sort both strings and compare. If any sorted window matches the sorted s1, return true.

target = sorted(s1)

for i in range(len(s2) - len(s1) + 1):
    window = s2[i:i + len(s1)]
    if sorted(window) == target:    # sort every window
        return True

return False

Sorting each window takes O(k log k) where k is the length of s1. With n windows total, that's O(n * k log k). You can compare two windows using frequency counts in O(k), and when you slide the window by one, you only need to update two characters, making each slide O(1).

Spotting the pattern

This is a Sliding Window problem. The key question to ask yourself:

How do I check if a chunk of s2 is a rearrangement of s1 without testing every possible ordering?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.