LeetCode 567: Permutation in String Solution

Master LeetCode problem 567 (Permutation in String), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

567. Permutation in String

Medium

Hash Table Two Pointers String Sliding Window

Problem Explanation

Explanation

To solve this problem, we can use a sliding window approach. We can maintain a count of characters in s1 and a sliding window of the same length as s1 in s2. We iterate through s2, updating the character counts in the window. At each step, we check if the counts in the window match the counts of s1. If they do, we return true. If not, we slide the window by removing the leftmost character and adding the rightmost character. We continue this process until we reach the end of s2. If we don't find a match, we return false.

Algorithm:

Create two arrays countS1 and countWindow to store the counts of characters in s1 and the current window in s2.
Initialize the counts of characters in s1.
Iterate through s2, updating the count of characters in the window.
At each step, check if the counts in the window match the counts of s1.
If the counts match, return true.
If not, slide the window by removing the leftmost character and adding the rightmost character.
Continue this process until the end of s2. If no match is found, return false.

Time Complexity: O(n), where n is the length of s2. Space Complexity: O(1) since the count arrays have a fixed size of 26 for lowercase English letters.

Solution Code

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length())
            return false;
        
        int[] countS1 = new int[26];
        int[] countWindow = new int[26];
        
        for (int i = 0; i < s1.length(); i++) {
            countS1[s1.charAt(i) - 'a']++;
            countWindow[s2.charAt(i) - 'a']++;
        }
        
        for (int i = 0; i < s2.length() - s1.length(); i++) {
            if (Arrays.equals(countS1, countWindow))
                return true;
            
            countWindow[s2.charAt(i) - 'a']--;
            countWindow[s2.charAt(i + s1.length()) - 'a']++;
        }
        
        return Arrays.equals(countS1, countWindow);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 567 (Permutation in String)?

This page provides optimized solutions for LeetCode problem 567 (Permutation in String) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 567 (Permutation in String)?

The time complexity for LeetCode 567 (Permutation in String) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 567 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 567 in Java, C++, or Python.

Back to LeetCode Solutions