567. Permutation in String

Jump to Solution: Python Java C++ JavaScript C#

Problem Description

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

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 <= 10⁴
s1 and s2 consist of lowercase English letters.

Solution

Python Solution

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
        
        # Create frequency maps
        s1_count = [0] * 26
        s2_count = [0] * 26
        
        # Initialize first window
        for i in range(len(s1)):
            s1_count[ord(s1[i]) - ord('a')] += 1
            s2_count[ord(s2[i]) - ord('a')] += 1
        
        # Check first window
        if s1_count == s2_count:
            return True
        
        # Slide window
        for i in range(len(s1), len(s2)):
            # Remove leftmost character
            s2_count[ord(s2[i - len(s1)]) - ord('a')] -= 1
            # Add new character
            s2_count[ord(s2[i]) - ord('a')] += 1
            
            if s1_count == s2_count:
                return True
        
        return False

Time Complexity: O(n)

Where n is the length of s2. We traverse s2 once and array comparison is O(1) as size is fixed at 26.

Space Complexity: O(1)

We use two fixed-size arrays of length 26 for character frequencies.

Java Solution

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }
        
        // Create frequency maps
        int[] s1Count = new int[26];
        int[] s2Count = new int[26];
        
        // Initialize first window
        for (int i = 0; i < s1.length(); i++) {
            s1Count[s1.charAt(i) - 'a']++;
            s2Count[s2.charAt(i) - 'a']++;
        }
        
        // Check first window
        if (Arrays.equals(s1Count, s2Count)) {
            return true;
        }
        
        // Slide window
        for (int i = s1.length(); i < s2.length(); i++) {
            // Remove leftmost character
            s2Count[s2.charAt(i - s1.length()) - 'a']--;
            // Add new character
            s2Count[s2.charAt(i) - 'a']++;
            
            if (Arrays.equals(s1Count, s2Count)) {
                return true;
            }
        }
        
        return false;
    }
}

Time Complexity: O(n)

Where n is the length of s2. We traverse s2 once and array comparison is O(1) as size is fixed at 26.

Space Complexity: O(1)

We use two fixed-size arrays of length 26 for character frequencies.

C++ Solution

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        if (s1.length() > s2.length()) {
            return false;
        }
        
        // Create frequency maps
        vector s1Count(26, 0);
        vector s2Count(26, 0);
        
        // Initialize first window
        for (int i = 0; i < s1.length(); i++) {
            s1Count[s1[i] - 'a']++;
            s2Count[s2[i] - 'a']++;
        }
        
        // Check first window
        if (s1Count == s2Count) {
            return true;
        }
        
        // Slide window
        for (int i = s1.length(); i < s2.length(); i++) {
            // Remove leftmost character
            s2Count[s2[i - s1.length()] - 'a']--;
            // Add new character
            s2Count[s2[i] - 'a']++;
            
            if (s1Count == s2Count) {
                return true;
            }
        }
        
        return false;
    }
};

Time Complexity: O(n)

Where n is the length of s2. We traverse s2 once and vector comparison is O(1) as size is fixed at 26.

Space Complexity: O(1)

We use two fixed-size vectors of length 26 for character frequencies.

JavaScript Solution

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function(s1, s2) {
    if (s1.length > s2.length) {
        return false;
    }
    
    // Create frequency maps
    const s1Count = new Array(26).fill(0);
    const s2Count = new Array(26).fill(0);
    
    // Initialize first window
    for (let i = 0; i < s1.length; i++) {
        s1Count[s1.charCodeAt(i) - 97]++;
        s2Count[s2.charCodeAt(i) - 97]++;
    }
    
    // Check first window
    if (s1Count.every((val, idx) => val === s2Count[idx])) {
        return true;
    }
    
    // Slide window
    for (let i = s1.length; i < s2.length; i++) {
        // Remove leftmost character
        s2Count[s2.charCodeAt(i - s1.length) - 97]--;
        // Add new character
        s2Count[s2.charCodeAt(i) - 97]++;
        
        if (s1Count.every((val, idx) => val === s2Count[idx])) {
            return true;
        }
    }
    
    return false;
};

Time Complexity: O(n)

Where n is the length of s2. We traverse s2 once and array comparison is O(1) as size is fixed at 26.

Space Complexity: O(1)

We use two fixed-size arrays of length 26 for character frequencies.

C# Solution

public class Solution {
    public bool CheckInclusion(string s1, string s2) {
        if (s1.Length > s2.Length) {
            return false;
        }
        
        // Create frequency maps
        int[] s1Count = new int[26];
        int[] s2Count = new int[26];
        
        // Initialize first window
        for (int i = 0; i < s1.Length; i++) {
            s1Count[s1[i] - 'a']++;
            s2Count[s2[i] - 'a']++;
        }
        
        // Check first window
        if (Enumerable.SequenceEqual(s1Count, s2Count)) {
            return true;
        }
        
        // Slide window
        for (int i = s1.Length; i < s2.Length; i++) {
            // Remove leftmost character
            s2Count[s2[i - s1.Length] - 'a']--;
            // Add new character
            s2Count[s2[i] - 'a']++;
            
            if (Enumerable.SequenceEqual(s1Count, s2Count)) {
                return true;
            }
        }
        
        return false;
    }
}

Time Complexity: O(n)

Where n is the length of s2. We traverse s2 once and array comparison is O(1) as size is fixed at 26.

Space Complexity: O(1)

We use two fixed-size arrays of length 26 for character frequencies.

Approach Explanation

The solution uses sliding window technique with character frequency counting:

Key Insights:
- Sliding window
- Character frequency
- Window comparison
- Efficient updates
Algorithm Steps:
- Initialize counts
- Check first window
- Slide window
- Compare frequencies

Implementation Details:

Array initialization
Window management
Character counting
Array comparison

Optimization Insights:

Fixed-size arrays
Early termination
Efficient updates
Memory reuse

Edge Cases:

Empty strings
Single character
No permutation
Multiple matches