Permutation in String

This problem teaches the fixed-size sliding window. The window never changes size here. It just slides one step at a time. The interviewer wants to see if you can compare letter counts fast instead of checking every arrangement. Get the count idea and this becomes a clean little loop.

🎯 The Problem

You get two strings, s1 and s2. You have to say if s2 contains a permutation of s1.

• A permutation is the same letters in any order.
• So "abc", "bca", and "cab" are all permutations of each other.
• They use the same letters the same number of times.
• You are really asking: is there a window in s2, the same length as s1, with the same letters as s1?

Let us say s1 is "ab" and s2 is "eidbaooo". Look at the window "ba" inside s2. It has one a and one b, just like "ab". So the answer is true.

Input:  s1 = "ab", s2 = "eidbaooo"
Output: true

Explanation: s2 contains the window "ba", which is a permutation of "ab".

Here is the picture. We slide a window of length 2 across s2 and check the letters.

🐢 Approach 1: Sort Each Window (Brute Force)

Take every window of s2 the same length as s1, then sort it and compare.

The idea:

• Two strings sorted the same way are permutations.
• So sort each window and sort s1, then compare.

How it works:

• Slide a window of length k across s2.
• Sort the window letters and compare to sorted s1.
• Stop the moment they match.

Why it is weak:

• You sort every window from scratch.
• Sorting each window costs k log k.
• Time is O(n · k log k). Wasteful on long strings.

Here is the sort-each-window code:

def check_inclusion(s1, s2):
    target = sorted(s1)
    size = len(s1)
    for i in range(len(s2) - size + 1):
        if sorted(s2[i:i + size]) == target:
            return True
    return False

🐌 Approach 2: Rebuild Counts Each Window (Better)

The idea in one line: two strings are permutations when their letter counts match, so count instead of sort.

The idea:

• Skip sorting. Compare letter counts.
• Same counts means same letters in some order.

How it works:

• Build a count table for s1.
• For each window of s2, count its letters fresh.
• Compare the two count tables.

Why it is better:

• Comparing two count tables beats sorting.
• No k log k sort per window.

Why it is still weak:

• You recount all k letters for every window.
• That is still about O(n · k).

Here is the rebuild-counts code:

from collections import Counter


def check_inclusion(s1, s2):
    need = Counter(s1)
    size = len(s1)
    for i in range(len(s2) - size + 1):
        if Counter(s2[i:i + size]) == need:
            return True
    return False

⚡ Approach 3: Fixed-Size Sliding Window (Best)

The idea in one line: keep the window’s counts and update only two letters each time it slides one step.

The idea:

• The window here is fixed-size. Its length never changes.
• It only slides one step at a time.

How it works:

• Count the letters of s1 and of the first window.
• Slide one step: add the new right letter, remove the old left letter.
• Compare the count tables after each slide.

Why it is fast:

• Only two slots change per slide.
• Comparing two tables of 26 letters is a fixed small cost.
• So the whole loop is O(n).

Here is the fixed window sliding one step at a time across s2.

Steps to Solve

1. If s1 is longer than s2, return false right away.
2. Count the letters of s1. Count the letters of the first window of s2 with the same length.
3. If the two count tables match, return true.
4. Slide the window one step. Add the new right letter and remove the old left letter.
5. Compare the counts after each slide.
6. If you match, return true. If you reach the end with no match, return false.

#include <stdio.h>
#include <string.h>

int matches(int a[26], int b[26]) {
    for (int i = 0; i < 26; i++) if (a[i] != b[i]) return 0;
    return 1;
}

int checkInclusion(const char *s1, const char *s2) {
    int n1 = (int)strlen(s1), n2 = (int)strlen(s2);
    if (n1 > n2) return 0;                 // s1 cannot fit in s2

    int need[26] = {0}, window[26] = {0};
    for (int i = 0; i < n1; i++) {         // build the first window
        need[s1[i] - 'a']++;
        window[s2[i] - 'a']++;
    }
    if (matches(need, window)) return 1;

    for (int right = n1; right < n2; right++) {
        window[s2[right] - 'a']++;         // add the new right letter
        window[s2[right - n1] - 'a']--;    // remove the old left letter
        if (matches(need, window)) return 1;
    }
    return 0;
}

int main(void) {
    printf("%s\n", checkInclusion("ab", "eidbaooo") ? "true" : "false");
    return 0;
}

true

#include <iostream>
#include <string>
#include <vector>
using namespace std;

bool checkInclusion(const string &s1, const string &s2) {
    int n1 = (int)s1.size(), n2 = (int)s2.size();
    if (n1 > n2) return false;             // s1 cannot fit in s2

    vector<int> need(26, 0), window(26, 0);
    for (int i = 0; i < n1; i++) {         // build the first window
        need[s1[i] - 'a']++;
        window[s2[i] - 'a']++;
    }
    if (need == window) return true;

    for (int right = n1; right < n2; right++) {
        window[s2[right] - 'a']++;         // add the new right letter
        window[s2[right - n1] - 'a']--;    // remove the old left letter
        if (need == window) return true;
    }
    return false;
}

int main() {
    cout << (checkInclusion("ab", "eidbaooo") ? "true" : "false") << endl;
    return 0;
}

true

import java.util.Arrays;

public class PermutationInString {
    public static boolean checkInclusion(String s1, String s2) {
        int n1 = s1.length(), n2 = s2.length();
        if (n1 > n2) return false;             // s1 cannot fit in s2

        int[] need = new int[26], window = new int[26];
        for (int i = 0; i < n1; i++) {         // build the first window
            need[s1.charAt(i) - 'a']++;
            window[s2.charAt(i) - 'a']++;
        }
        if (Arrays.equals(need, window)) return true;

        for (int right = n1; right < n2; right++) {
            window[s2.charAt(right) - 'a']++;          // add right letter
            window[s2.charAt(right - n1) - 'a']--;     // remove left letter
            if (Arrays.equals(need, window)) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(checkInclusion("ab", "eidbaooo"));
    }
}

true

def check_inclusion(s1, s2):
    n1, n2 = len(s1), len(s2)
    if n1 > n2:                       # s1 cannot fit in s2
        return False

    need = [0] * 26                   # letter counts of s1
    window = [0] * 26                 # letter counts of current window
    for i in range(n1):               # build the first window
        need[ord(s1[i]) - ord('a')] += 1
        window[ord(s2[i]) - ord('a')] += 1
    if need == window:                # first window already matches
        return True

    for right in range(n1, n2):       # slide one step at a time
        window[ord(s2[right]) - ord('a')] += 1        # add right letter
        window[ord(s2[right - n1]) - ord('a')] -= 1   # remove left letter
        if need == window:            # counts match, found it
            return True
    return False


s1 = "ab"
s2 = "eidbaooo"
print(check_inclusion(s1, s2))

True

function checkInclusion(s1, s2) {
  const n1 = s1.length, n2 = s2.length;
  if (n1 > n2) return false;          // s1 cannot fit in s2

  const need = new Array(26).fill(0); // letter counts of s1
  const window = new Array(26).fill(0); // counts of current window
  const base = "a".charCodeAt(0);
  for (let i = 0; i < n1; i++) {      // build the first window
    need[s1.charCodeAt(i) - base]++;
    window[s2.charCodeAt(i) - base]++;
  }
  const same = () => need.every((v, i) => v === window[i]);
  if (same()) return true;

  for (let right = n1; right < n2; right++) {
    window[s2.charCodeAt(right) - base]++;        // add right letter
    window[s2.charCodeAt(right - n1) - base]--;   // remove left letter
    if (same()) return true;
  }
  return false;
}

const s1 = "ab";
const s2 = "eidbaooo";
console.log(checkInclusion(s1, s2));

true

Let us walk through the Python version line by line and see why each line is there.

n1, n2 = len(s1), len(s2) stores both lengths. if n1 > n2: return False is a quick exit. If s1 is longer than s2, no window can hold it.

need = [0] * 26 and window = [0] * 26 are two count lists, one slot per letter a to z. need holds the counts for s1. window holds the counts for the part of s2 we are looking at.

for i in range(n1): builds the very first window. It adds each letter of s1 to need and each matching-length letter of s2 to window. ord(s1[i]) - ord('a') turns a letter into a slot number from 0 to 25.

if need == window: return True checks the first window. If the two count lists are equal, the window is a permutation of s1, so we are done.

for right in range(n1, n2): slides the window one step at a time. right is the new letter coming in on the right.

window[ord(s2[right]) - ord('a')] += 1 adds the new right letter to the window counts. window[ord(s2[right - n1]) - ord('a')] -= 1 removes the letter that just fell off the left edge. Only two slots change per slide, so this is cheap.

if need == window: return True checks the counts after the slide. A match means we found a permutation.

return False runs if we slid all the way to the end with no match.

⏱️ Time and Space Complexity

The brute force sorts every window, so it is slow. The fixed-size sliding window updates only two letters per step and compares small count tables. So it runs in O(n) time. The memory is two count tables of 26 letters, which is a fixed small amount.

🧩 Key Takeaways

• ✅ Two strings are permutations when they have the same letter counts. Compare counts, not order.
• ✅ The window here is fixed-size. It never grows or shrinks, it only slides one step.
• ✅ Each slide adds one letter on the right and removes one on the left, so it stays cheap.
• ✅ Comparing two count tables of 26 letters is a small fixed cost, so the loop is O(n).
• ✅ Say the sort-and-compare idea first, then explain how counts remove the sorting. That shows your thinking.

🚀 What’s Next?

• Minimum Window Substring
• Longest Substring Without Repeating Characters