[Leetcode] 567. Permutation in String

https://leetcode.com/problems/longest-repeating-character-replacement/description/

initial

just typical sliding window way but i was lazy i was building sliding window each time

btw v careful to i<=s2.length(), not i<s2.length() or u will not account the last permuataion possibility

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        Map<Character,Integer> s1_map=toMap(s1);
        int k = s1.length();
        for(int i=k;i<=s2.length();i++){
            String substring = s2.substring(i-k,i);
            Map<Character,Integer> s2_map = toMap(substring);
            if(s1_map.equals(s2_map)) return true;
        }
        return false;
    }

    public Map<Character,Integer> toMap(String in){
        Map<Character,Integer> map = new HashMap<>();
        for(Character c: in.toCharArray()){
            map.put(c,map.getOrDefault(c,0)+1);
        }
        return map;
    }
}

sol

instead of rebuilding just use nums[] array

def checkInclusion(s1: str, s2: str) -> bool:
    if len(s1) > len(s2):
        return False

    s1_counts = [0] * 26
    s2_counts = [0] * 26

    # Initial count for the first window
    for i in range(len(s1)):
        s1_counts[ord(s1[i]) - ord('a')] += 1
        s2_counts[ord(s2[i]) - ord('a')] += 1

    # Slide the window
    for i in range(len(s2) - len(s1)):
        if s1_counts == s2_counts:
            return True
        
        # Move window: Add next char, remove leftmost char
        s2_counts[ord(s2[i + len(s1)]) - ord('a')] += 1
        s2_counts[ord(s2[i]) - ord('a')] -= 1

    # Check the very last window
    return s1_counts == s2_counts

complexity

n*k for rebuilding dictionary each time
o(26) space