Permutation in String

Problem Statement

In this problem, you're given two strings, s1 and s2. The challenge is to determine whether any permutation of the string s1 appears as a substring within s2. Simply put, the task is to check if by rearranging the letters of s1, the resultant string could be found as a continuous segment (substring) in s2. If such a permutation exists, the function should return true; otherwise, it should return false.

Examples

Example 1

Input:

s1 = "ab", s2 = "eidbaooo"

Output:

true

Explanation:

s2 contains one permutation of s1 ("ba").

Example 2

Input:

s1 = "ab", s2 = "eidboaoo"

Output:

false

Constraints

• 1 <= s1.length, s2.length <= 104
• s1 and s2 consist of lowercase English letters.

Approach and Intuition

Understanding whether one string's permutation is a substring of another can be effectively tackled using a sliding window technique combined with character frequency counts. Here’s an intuitive step-by-step approach:

1. Compare the length of s1 with s2. If s1 is longer than s2, return false since a substring can't be longer than the string it is being checked against.

2. Create a frequency count for characters in s1. This count will represent the exact character composition any substring in s2 must have to be a permutation of s1.

3. Initialize the sliding window on s2 with the size equal to the length of s1. This window will traverse s2 from beginning to end.

4. As the window moves:

   • If entering the window, increase the count of the new character from s2 in a current window frequency count.
   • If leaving the window, decrease the count of the outgoing character from s2.
   • After adjusting counts, compare the current window's character frequency count with that of s1.

5. If at any point the frequency counts match, return true because this means a permutation of s1 is currently in the sliding window in s2.

This approach ensures we only check continuous substrings of s2 that are exactly the same length as s1, and we efficiently update our checks as we move the window one character at a time. Additionally, the use of character frequency counts abstracts the problem of actual string arrangement into simpler numerical comparisons.

The constraints provided—1 <= s1.length, s2.length <= 10^4—suggest a need for an efficient approach, as the potential search space (for naive substring search) could be massive. Our proposed method leverages constant time (O(1)) operations (decrement/increment of counts) executed within a linear traversal of s2, making it apt for the problem's requirements.

Solutions

public class Solution {
    public boolean permuteInclusion(String perm, String text) {
        if (perm.length() > text.length())
            return false;
        int[] permFreq = new int[26];
        int[] textFreq = new int[26];
        for (int i = 0; i < perm.length(); i++) {
            permFreq[perm.charAt(i) - 'a']++;
            textFreq[text.charAt(i) - 'a']++;
        }
    
        int match = 0;
        for (int i = 0; i < 26; i++) {
            if (permFreq[i] == textFreq[i])
                match++;
        }
                
        for (int i = 0; i < text.length() - perm.length(); i++) {
            int left = text.charAt(i) - 'a';
            int right = text.charAt(i + perm.length()) - 'a';
                
            if (match == 26)
                return true;
                
            textFreq[right]++;
            if (textFreq[right] == permFreq[right])
                match++;
            else if (textFreq[right] == permFreq[right] + 1)
                match--;
                
            textFreq[left]--;
            if (textFreq[left] == permFreq[left])
                match++;
            else if (textFreq[left] == permFreq[left] - 1)
                match--;
        }
        return match == 26;
    }
}