Permutation in String medium

Problem Statement

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 the anagrams of s1 is a substring of s2.

Example 1:

Input: s1 = "ab", s2 = "eidbaooo" Output: true Explanation: s2 contains the permutation "ab" of s1.

Example 2:

Input: s1 = "ab", s2 = "eidboaoo" Output: false

Steps and Explanation:

The core idea is to use a sliding window approach and character frequency counting. We'll maintain a window of the same size as s1 within s2. We'll count the character frequencies in s1 and compare them to the frequencies within the sliding window. If they match, we've found a permutation.

1. Frequency Count of s1: Create a frequency map (HashMap in Java) for s1, storing the count of each character.

2. Sliding Window: Initialize a sliding window of size equal to the length of s1. Iterate through s2 using this window.

3. Frequency Count of Window: For each position of the window, create a frequency map for the characters within the window.

4. Comparison: Compare the frequency map of s1 with the frequency map of the current window. If they are identical, we have found a permutation.

5. Sliding: Move the window one position to the right, updating the frequency count of the window. Subtract the frequency of the character leaving the window and add the frequency of the character entering the window.

6. Return: If a permutation is found within the iteration, return true. Otherwise, return false after the loop completes.

Code (Java)

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) return false; // Optimization: s1 cannot be a permutation if it's longer

        Map<Character, Integer> s1Freq = new HashMap<>();
        for (char c : s1.toCharArray()) {
            s1Freq.put(c, s1Freq.getOrDefault(c, 0) + 1);
        }

        Map<Character, Integer> windowFreq = new HashMap<>();
        int windowStart = 0;
        int windowEnd = 0;
        int matched = 0; // Count of characters matched between window and s1

        while (windowEnd < s2.length()) {
            char c = s2.charAt(windowEnd);
            windowFreq.put(c, windowFreq.getOrDefault(c, 0) + 1);

            if (s1Freq.containsKey(c) && windowFreq.get(c).intValue() == s1Freq.get(c).intValue()) {
                matched++;
            }

            if (windowEnd - windowStart + 1 == s1.length()) {
                if (matched == s1Freq.size()) return true; // Permutation found

                char leftChar = s2.charAt(windowStart);
                windowFreq.put(leftChar, windowFreq.get(leftChar) - 1);
                if (s1Freq.containsKey(leftChar) && windowFreq.get(leftChar) < s1Freq.get(leftChar)) {
                    matched--;
                }
                windowStart++;
            }
            windowEnd++;
        }

        return false; // No permutation found
    }
}

Complexity Analysis

• Time Complexity: O(m + n), where n is the length of s2 and m is the length of s1. We iterate through s2 once. The operations within the loop are constant time on average for hashmap operations.

• Space Complexity: O(1). The space used by the hashmaps is bounded by the size of the alphabet (26 for lowercase English letters), which is considered constant.