Permutation in String Algorithm Solution

The permutation in string problem requires determining whether any permutation of a given pattern exists as a substring in a target string. This classic algorithmic challenge demonstrates the application of sliding window techniques for efficient string matching.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can the input strings contain any characters or are they restricted to lowercase letters only?
2. What is the expected time complexity constraint - are we looking for O(n) or O(n log n) solution?
3. Should we modify the input strings or work with copies?
4. How should we handle edge cases like empty strings or when s1 is longer than s2?
5. Do we need to return all valid permutations or just indicate if one exists?

Restatement in my own words: Given two strings s1 and s2, determine whether any permutation of s1 exists as a substring in s2. A permutation means the same characters with the same frequencies, just arranged differently.

Input/Output specification:

• Input: Two strings s1 and s2 where 1 ≤ length(s1) ≤ length(s2) ≤ 10⁴
• Output: Boolean indicating whether any permutation of s1 appears as a substring in s2

Key constraints and assumptions:

• Both strings contain only lowercase English letters (assuming this from typical problem setup)
• We can modify the input strings if needed
• The solution should handle edge cases gracefully (empty strings, single character, etc.)
• We're looking for an efficient solution rather than brute force

Data shape and hidden structure: The problem has a sliding window pattern where we need to check if any substring of s2 with length equal to s1 has the same character frequency as s1. This suggests using a frequency map or character count approach with a fixed-size sliding window.

The core insight is that we don't need to generate all permutations (which would be O(m!)) but instead can use character frequency matching in a sliding window approach, reducing the complexity to O(n) where n is the length of s2.

2. Pattern Recognition

The problem asks us to determine whether any permutation of a given string p exists as a substring in another string s. This is fundamentally about pattern matching with flexibility in character arrangement.

Key signals that point to this being a sliding window problem:

• We're looking for a substring of fixed length (equal to the length of p)
• The substring must contain exactly the same characters as p, just rearranged
• We need to check all possible contiguous substrings of that fixed size

Why this fits the sliding window pattern: The core insight is that we're looking for a contiguous substring of s that has the exact same character frequencies as string p. This is a classic use case for the sliding window technique with frequency counting.

The core insight needed to solve it: Instead of generating all permutations (which would be factorial time), we can use a sliding window approach where we maintain character frequency counts for:

1. The pattern string p (target frequencies)
2. A window of size p.length() in string s

If at any point these two frequency maps match, we've found a valid permutation.

This pattern appears in many string matching problems where we need to find substrings with specific character compositions rather than exact string matches.

3. Approach Evolution

My first instinct is to check if one string is a permutation of another by comparing character frequencies. But that would be O(n²) time complexity if I try to check every substring of s2 against s1's character count, because for each position in s2 I'd need to count characters in a window of length equal to s1.

Let me think about how to optimize this. I notice that if I maintain a sliding window of size equal to s1's length over s2, I can keep track of character frequencies in that window and compare it with s1's character frequency. This is a classic sliding window pattern where I can reduce the time complexity from O(n²) to O(n).

The key insight is that instead of recalculating character counts for every substring, I can maintain a running window and efficiently update the character count as I slide the window forward. This way, I only need to process each character in s2 once.

I'll use a sliding window approach with two pointers. The window size will be exactly the length of s1, and I'll maintain character frequency counts for both s1 and the current window in s2. When these counts match, I've found a permutation.

The invariant I need to maintain is that the character frequency count of the current window in s2 matches exactly with the character frequency count of s1. This invariant holds as long as I properly update the window counts when sliding.

Let me walk through this more carefully:

1. First, I'll create a frequency map for s1
2. Then I'll use a sliding window of size s1.length() over s2
3. For each window, I'll maintain a frequency map and compare it with s1's frequency map
4. If they match, I found a permutation

This approach is O(n) time where n is the length of s2, and O(1) space since there are at most 26 lowercase letters.

4. Data Structure Choice

For this permutation problem, I'll use a sliding window approach with frequency counting.

Primary Data Structures

1. HashMap<Character, Integer> - Used to maintain frequency counts of characters in the pattern string and current window

   • Why needed: We need to track character frequencies to efficiently check if a window is a permutation
   • Time impact: O(1) average lookup and update operations
   • Space impact: O(k) where k is the number of unique characters in the pattern

2. Two Pointers (integers) - Used to maintain the sliding window bounds

   • Why needed: To efficiently move the window forward and maintain its size
   • Time impact: O(1) operations for pointer movement
   • Space impact: O(1) additional space

Why This Choice Is Optimal

The HashMap approach provides the perfect balance between:

• Efficient character frequency tracking: O(1) average time for updates and lookups
• Minimal space overhead: Only stores necessary character frequencies, not entire substrings
• Clean implementation: Easy to understand and maintain

Helper Structures

I'll also use:

• Integer variables to track window size and match count for optimization
• Standard Java collections (HashMap) for clean, readable code

This combination allows us to maintain a constant-size window while efficiently checking permutation conditions without storing unnecessary intermediate data. The sliding window pattern naturally fits this approach since we're looking for a substring of fixed size that matches character frequencies.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to demonstrate how it works:

Example: s1 = "ab", s2 = "eidbaooo"

Step 1: Initialize sliding window

• s1 length = 2, so we need a window of size 2 in s2
• First window: s2.substring(0, 2) = "ei"
• Character counts for s1: {a:1, b:1}
• Character counts for window: {e:1, i:1}

Step 2: Slide the window

• Move window to position 1: s2.substring(1, 3) = "id"
• Character counts for window: {i:1, d:1}
• No match yet

Step 3: Continue sliding

• Move window to position 2: s2.substring(2, 4) = "db"
• Character counts for window: {d:1, b:1}
• Still no match

Step 4: Continue sliding

• Move window to position 3: s2.substring(3, 5) = "ba"
• Character counts for window: {b:1, a:1}
• MATCH FOUND! Window character counts exactly match s1 character counts

Step 5: Return result

• Since we found a matching window, return true

Key points in the walkthrough:

• We maintain a sliding window of size equal to s1.length()
• At each step, we compare character frequency maps
• The window slides one position at a time from left to right
• When character frequencies match exactly, we've found our permutation

Edge case handling:

• If s2 is shorter than s1, we'd never enter the loop and return false
• If s2 is exactly the same length as s1, we check once and return result
• The algorithm handles duplicate characters correctly through frequency counting

The algorithm terminates correctly because:

1. We process each valid window position once
2. Character frequency comparison is O(1) since we're comparing fixed-size maps (at most 26 characters)
3. We return immediately when a match is found, avoiding unnecessary processing

6. Java Solution

public class Solution {
    public boolean checkInclusion(String s1, String s2) {
        // Handle edge cases
        if (s1 == null || s2 == null || s1.length() > s2.length()) {
            return false;
        }
        
        // Create frequency map for s1
        int[] s1Freq = new int[26];
        for (char c : s1.toCharArray()) {
            s1Freq[c - 'a']++;
        }
        
        int windowSize = s1.length();
        int left = 0;
        int right = 0;
        int matches = 0; // Count of characters that match frequency requirement
        
        // Sliding window over s2
        int[] windowFreq = new int[26];
        
        while (right < s2.length()) {
            // Expand window to the right
            char rightChar = s2.charAt(right);
            int charIndex = rightChar - 'a';
            windowFreq[charIndex]++;
            
            // Check if this character now matches the required frequency
            if (windowFreq[charIndex] == s1Freq[charIndex]) {
                matches++;
            } else if (windowFreq[charIndex] == s1Freq[charIndex] + 1) {
                // This character now exceeds required frequency
                matches--;
            }
            
            // Shrink window from left if it's larger than s1 length
            if (right - left + 1 > windowSize) {
                char leftChar = s2.charAt(left);
                int leftCharIndex = leftChar - 'a';
                
                // Check if removing this character breaks a match
                if (windowFreq[leftCharIndex] == s1Freq[leftCharIndex]) {
                    matches--;
                }
                
                windowFreq[leftCharIndex]--;
                left++;
            }
            
            // Check if we have a valid permutation
            if (matches == 26) {
                return true;
            }
            
            right++;
        }
        
        return false;
    }
}

This solution uses a sliding window approach with frequency counting to efficiently check if any permutation of s1 exists as a substring in s2. The key insight is to maintain character frequency counts and track how many characters match their required frequencies, allowing us to quickly determine when we have a valid permutation without checking all permutations explicitly.

7. Complexity Analysis

Time Complexity: O(n) where n is the length of s2. We iterate through s2 once with two pointers, and each character is processed at most twice (once by right pointer, once by left pointer). The inner while loop operations are amortized O(1) since each character is added/removed from the sliding window at most once.

Space Complexity: O(k) where k is the size of the character set (at most 26 for lowercase English letters). We maintain a HashMap with at most k entries for character frequencies, and the sliding window variables use constant space.

Why these bounds are correct:

• The algorithm uses a classic sliding window technique with two pointers
• Each character is processed at most twice (once added to window, once removed)
• The HashMap operations (put, get, remove) are O(1) average case for the character set size
• The total number of operations scales linearly with input size

Optimality: This solution is optimal for the problem as it achieves linear time complexity. Since we must examine each character in s2 at least once to determine if a permutation exists, O(n) is the theoretical lower bound. Our solution matches this bound exactly.

The approach is near-optimal because:

1. We avoid sorting or generating permutations which would be O(n log n) or worse
2. We use a single pass with efficient data structures
3. The sliding window technique is the most appropriate pattern for this substring matching problem

8. Edge Cases & Pitfalls

Empty and minimal inputs

• Empty s1 string should return true (empty pattern matches empty window)
• Empty s2 string should return false (no window to check)
• Single character strings require careful boundary handling

Duplicate values and repeated states

• When s1 contains duplicate characters, sliding window must maintain exact character counts
• The algorithm must track frequency of each character precisely - not just presence of characters
• Example: s1 = "aab" vs s2 = "abab" - window must contain exactly 2 a's and 1 b

Boundary conditions

• When s1.length() > s2.length() - immediately return false
• Window size must be exactly s1.length() throughout execution
• Index bounds checking is critical when accessing character arrays

Common implementation mistakes

• Incorrect frequency tracking: Using Set instead of HashMap or int[] for character counting
• Off-by-one errors: Not properly handling window expansion/contraction
• Missing character frequency updates: Failing to decrement counts when removing characters from window
• Not resetting state properly: When invalidating windows, not clearing character counts correctly
• Array bounds issues: Accessing s2 indices beyond array length when window slides

// Example of incorrect approach:
// HashMap<Character, Integer> charCount = new HashMap<>();
// // Missing proper decrement when sliding window removes character
// charCount.put(ch, charCount.get(ch) - 1); // Could throw NPE if key doesn't exist

The most critical pitfall is maintaining proper character frequency counts throughout the sliding window process, as any error in counting will cause false positives or negatives in permutation detection.

9. Alternative Approaches

There are several alternative approaches to solving the permutation in string problem, each with different trade-offs:

1. Sliding Window with Character Frequency Maps Instead of using a single counter, we could maintain separate frequency maps for the pattern and current window. For each window position, we compare the two maps directly to check if they're identical. This approach is more explicit about character counting but requires additional space for the frequency maps and has higher constant factors due to map comparisons.

2. Sorting-Based Approach We could sort the pattern string and for each window, sort the substring and compare it with the sorted pattern. This approach has O(n * m log m) time complexity where n is string length and m is pattern length, making it less efficient than our sliding window solution. However, it's conceptually simpler to understand.

3. Backtracking with Permutation Generation Generate all permutations of the pattern string and check if any permutation exists as a substring. This approach has factorial time complexity O(m!) where m is pattern length, making it infeasible for large patterns and not suitable for this problem's constraints.

4. Rolling Hash Approach Use rolling hash techniques to compute hash values of pattern and all substrings of matching length. While this can achieve O(n) time complexity, it introduces the risk of hash collisions and requires careful handling of modulo operations. This adds implementation complexity without significant benefit for this specific problem.

Our chosen sliding window approach with a single counter is optimal because it maintains O(n) time complexity while using minimal space and avoiding the overhead of map operations or hash computations. The single counter approach is cleaner, more readable, and has better practical performance characteristics for this specific use case.

10. Test Cases

public class PermutationInString {
    public static void main(String[] args) {
        // Test case 1: Basic permutation exists
        // s1 = "ab", s2 = "eidbaooo"
        // Expected: true (permutation "ba" found at index 1)
        System.out.println("Test 1: " + new PermutationInString().checkInclusion("ab", "eidbaooo"));
        
        // Test case 2: No permutation exists
        // s1 = "ab", s2 = "eidboaoo"
        // Expected: false (no permutation of "ab" in s2)
        System.out.println("Test 2: " + new PermutationInString().checkInclusion("ab", "eidboaoo"));
        
        // Test case 3: Empty string s1
        // s1 = "", s2 = "abc"
        // Expected: true (empty string is permutation of empty string)
        System.out.println("Test 3: " + new PermutationInString().checkInclusion("", "abc"));
        
        // Test case 4: s1 longer than s2
        // s1 = "abc", s2 = "ab"
        // Expected: false (impossible case)
        System.out.println("Test 4: " + new PermutationInString().checkInclusion("abc", "ab"));
        
        // Test case 5: Exact match
        // s1 = "abc", s2 = "abc"
        // Expected: true (exact match)
        System.out.println("Test 5: " + new PermutationInString().checkInclusion("abc", "abc"));
        
        // Test case 6: Single character
        // s1 = "a", s2 = "abbb"
        // Expected: true (permutation "a" found)
        System.out.println("Test 6: " + new PermutationInString().checkInclusion("a", "abbb"));
        
        // Test case 7: All same characters
        // s1 = "aaa", s2 = "aaaaaa"
        // Expected: true (permutation exists)
        System.out.println("Test 7: " + new PermutationInString().checkInclusion("aaa", "aaaaaa"));
        
        // Test case 8: Complex permutation
        // s1 = "adc", s2 = "dcda"
        // Expected: true (permutation "acd" found)
        System.out.println("Test 8: " + new PermutationInString().checkInclusion("adc", "dcda"));
    }
}

Sample test cases include:

1. Basic case with valid permutation at index 1
2. Case where no permutation exists
3. Edge case with empty pattern string
4. Impossible case where pattern is longer than target
5. Exact match scenario
6. Single character pattern
7. Repeated characters in both strings
8. Complex permutation with different character order

These test cases cover various scenarios including edge cases, boundary conditions, and typical usage patterns to ensure robust solution behavior.

11. Final Summary

The core insight is that we need to find if any permutation of string s1 exists as a substring in s2, which can be efficiently solved using a sliding window approach with character frequency counting. By maintaining a fixed-size window of length equal to s1 and comparing character frequencies, we can determine permutation existence in linear time.

This solution works because permutations of a string have identical character frequency distributions - if we can find a substring in s2 with the exact same character counts as s1, then that substring is guaranteed to be a permutation of s1. The sliding window approach efficiently checks all possible substrings without redundant computations.

The solution is optimal with O(n) time complexity where n is the length of s2, and O(1) space complexity since we only maintain frequency arrays of fixed size 26 for lowercase letters. This is near-optimal because we must examine each character in s2 at least once to determine if any permutation exists, making the linear bound unavoidable.