algoadvance

Leetcode 567. Permutation in String

Problem Statement

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

In other words, one of the first string’s permutations is the substring of the second string.

Clarifying Questions

  1. Input Constraints:
    • Are the strings s1 and s2 limited to lowercase English letters only?
    • What are the length constraints for s1 and s2?
  2. Output Requirements:
    • Should the function return a boolean value?

Once confirmed:

  1. s1 and s2 consist of lowercase English letters.
  2. Length of s1 and s2 can be up to 10,000.

Strategy

To solve the problem, we can use a sliding window technique along with character frequency counting:

  1. Character Count Arrays: Create two arrays to store the frequency of characters for s1 and for the current window in s2.

  2. Initial Comparison: Initialize both character count arrays. Count the frequency of characters for the first window in s2 of size equal to s1. Compare the frequency arrays.

  3. Sliding Window: Slide the window across s2 by one character at a time:
    • Update the count array by removing the leftmost character of the previous window and adding the rightmost character of the current window.
    • Compare the updated count array with the frequency array of s1.
  4. Comparison Function: If the count arrays match at any point, it means there is a permutation of s1 in s2, and we return true. If we finish sliding through s2 without finding a match, return false.

Code

public class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int len1 = s1.length();
        int len2 = s2.length();
        
        if (len1 > len2) {
            return false;
        }
        
        int[] count1 = new int[26];
        int[] count2 = new int[26];
        
        // Initialize the character count arrays
        for (int i = 0; i < len1; i++) {
            count1[s1.charAt(i) - 'a']++;
            count2[s2.charAt(i) - 'a']++;
        }
        
        // Initial comparison
        if (matches(count1, count2)) {
            return true;
        }
        
        // Sliding window
        for (int i = len1; i < len2; i++) {
            count2[s2.charAt(i) - 'a']++;
            count2[s2.charAt(i - len1) - 'a']--;
            if (matches(count1, count2)) {
                return true;
            }
        }
        
        return false;
    }
    
    private boolean matches(int[] count1, int[] count2) {
        for (int i = 0; i < 26; i++) {
            if (count1[i] != count2[i]) {
                return false;
            }
        }
        return true;
    }
}

Time Complexity

Overall, the time complexity is O(Len1 + Len2), which is linear with respect to the combined length of the two strings.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI