Crack the Backend

Problem Statement

Given two strings s1 and s2, return true if s2 contains a permutation of s1 — that is, if there exists a contiguous substring of s2 that has the same character counts as s1 (an anagram of s1).

The substring in s2 must be contiguous and of length exactly s1.length().
If s1 is longer than s2, return false.
Only lowercase English letters are typically considered; the idea extends to any finite alphabet.

Key Observations

A permutation of s1 is uniquely determined by its character counts. So we need a contiguous block in s2 of length |s1| whose frequency map equals that of s1.
We can use a fixed-size sliding window of length |s1| in s2. As we slide by one position, we remove one character from the left and add one on the right; update the window's frequency map and compare with s1's map (or maintain a "match" count to avoid full comparison each time).
To avoid comparing two full arrays every step: maintain the window's freq and a counter "how many characters have the same count in window as in s1"; when that counter equals the number of distinct characters (or total agreement), we have a permutation.

Approach

High-level: Build the frequency map for s1. Slide a window of length |s1| over s2, maintaining the window's character counts. When the window's counts match s1's counts, return true. Use a single "match" counter (e.g. how many chars have correct count) for O(1) check per step.

Steps:

If s1.length() > s2.length(), return false. Build freq for s1.
Initialize the first window s2[0..len(s1)-1] and its freq; compute initial "match" count (how many chars have window count == s1 count).
For each new position: remove left char (update counts and match), add right char (update counts and match). If match indicates full agreement, return true.
Return false after scanning.

Implementation

Java

public boolean checkInclusion(String s1, String s2) {

    if (s1.length() > s2.length()) {
        return false;
    }

    int[] freq = new int[26];

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

    int left = 0, match = 0;

    for (int right = 0; right < s2.length(); right++) {
        int r = s2.charAt(right) - 'a';

        if (--freq[r] >= 0) {
            match++;
        }

        if (right - left + 1 > s1.length()) {
            int l = s2.charAt(left) - 'a';

            if (freq[l]++ >= 0) {
                match--;
            }

            left++;
        }

        if (match == s1.length()) {
            return true;
        }
    }

    return false;
}

Test Cases

Example 1

Input

s1 = "ab", s2 = "eidbaooo"

Expected

true

Explanation

"ba" is a permutation of "ab".

Complexity Analysis

Time: O(n + m).
Space: O(1).

Follow-ups

Find all start indices of permutations of s1 in s2.