Permutation in String

Problem Link

Permutation in String – LeetCode #567

Problem Statement

You are given two strings s1 and s2.
Return true if s2 contains a permutation of s1, else return false.

In other words, check if any substring of s2 has the same character frequency as s1.

Examples

• Input: s1 = "ab", s2 = "eidbaooo"
  Output: true
  Explanation: The substring "ba" is a permutation of "ab".

• Input: s1 = "ab", s2 = "eidboaoo"
  Output: false
  Explanation: No permutation of "ab" exists as a substring.

Constraints

• 1 <= s1.length, s2.length <= 10⁴

• s1 and s2 consist of lowercase English letters only

Intuition

We need to check whether any substring of s2 (of length equal to s1) is a permutation of s1.

This is a Fixed-Size Sliding Window + Frequency Array Matching problem:

• A permutation has the same frequency of characters as the original string.

• So if we track the frequencies in both strings and compare them for each window, we can determine a match.

Instead of generating permutations explicitly (which is factorial time), we compare the frequency signatures of sliding windows.

Approach

1. If s1.length() > s2.length(), return false.

2. Initialize two frequency arrays:

   • s1Count for s1

   • s2Count for the current window in s2

3. Fill both arrays for the first window of size s1.length().

4. For each new character entering the window:

   • Compare s1Count with s2Count:

     • If they match, return true

   • Slide the window:

     • Decrement the count of the character that’s moving out

     • Increment the count of the character that’s coming in

5. Finally, check the last window (after the loop ends).

Java Code

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) return false;

        int[] s1Count = new int[26];
        int[] s2Count = new int[26];

        // Step 1: Initialize both frequency arrays
        for (int i = 0; i < s1.length(); i++) {
            s1Count[s1.charAt(i) - 'a']++;
            s2Count[s2.charAt(i) - 'a']++;
        }

        // Step 2: Slide the window
        for (int i = 0; i < s2.length() - s1.length(); i++) {
            if (matches(s1Count, s2Count)) return true;

            // Slide: remove leftmost, add rightmost
            s2Count[s2.charAt(i) - 'a']--;
            s2Count[s2.charAt(i + s1.length()) - 'a']++;
        }

        // Final check for last window
        return matches(s1Count, s2Count);
    }

    // Utility to compare two frequency arrays
    private boolean matches(int[] s1Count, int[] s2Count) {
        for (int i = 0; i < 26; i++) {
            if (s1Count[i] != s2Count[i]) return false;
        }
        return true;
    }
}

Time and Space Complexity

• Time Complexity: O(n * 26) = O(n)

  • n = length of s2

  • Each comparison is O(26) which is constant

• Space Complexity: O(1)

  • Two arrays of length 26 used (constant space)

Dry Run

Input:

s1 = "ab", s2 = "eidbaooo"

Steps:

• Initial s1Count: {a:1, b:1}

• First window: "ei" → not matching

• Second window: "id" → not matching

• Third window: "db" → not matching

• Fourth window: "ba" → matching → return true

Conclusion

This is a Fixed-Size Sliding Window + Hash Lookup (Frequency Arrays) problem.

Key insights:

• Sliding window helps avoid repeated recomputation.

• Comparing frequency arrays allows O(1) match checking.

• Efficient pattern for anagram/permutation substring checks.

This pattern is commonly reused in:

• Anagram finding (Find All Anagrams in a String)

• Anagram grouping/counting

• String permutation checks