[Leetcode] 424. Longest Repeating Character Replacement

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

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) return false;

        int[] s1Count = new int[26];
        int[] s2Count = new int[26];

        // Count frequency for s1 and first window of s2
        for (int i = 0; i < s1.length(); i++) {
            s1Count[s1.charAt(i) - 'a']++;
            s2Count[s2.charAt(i) - 'a']++;
        }

        // If first window matches
        if (matches(s1Count, s2Count)) return true;

        // Slide the window
        for (int i = s1.length(); i < s2.length(); i++) {
            s2Count[s2.charAt(i) - 'a']++; // Add new char
            s2Count[s2.charAt(i - s1.length()) - 'a']--; // Remove old char

            if (matches(s1Count, s2Count)) return true;
        }

        return false;
    }

    private boolean matches(int[] arr1, int[] arr2) {
        for (int i = 0; i < 26; i++) {
            if (arr1[i] != arr2[i]) return false;
        }
        return true;
    }
}

complexity

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