String Hashing and Anagrams

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    char[] sc = s.toCharArray();
    char[] tc = t.toCharArray();
    Arrays.sort(sc);
    Arrays.sort(tc);
    return Arrays.equals(sc, tc);
    // Time: O(n log n), Space: O(n)
}

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] freq = new int[26];
    for (char c : s.toCharArray()) freq[c - 'a']++;
    for (char c : t.toCharArray()) freq[c - 'a']--;
    for (int f : freq) if (f != 0) return false;
    return true;
    // Time: O(n), Space: O(1) — fixed 26 entries
}

// Canonical key: sorted version of the word
public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> groups = new HashMap<>();
    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars); // canonical key
        groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(groups.values());
}
// ["eat","tea","tan","ate","nat","bat"]
// → [["eat","tea","ate"],["tan","nat"],["bat"]]

public boolean checkInclusion(String s1, String s2) {
    if (s1.length() > s2.length()) return false;
    int[] need = new int[26];
    int[] have = new int[26];
    for (char c : s1.toCharArray()) need[c - 'a']++;

    int k = s1.length();
    for (int i = 0; i < s2.length(); i++) {
        have[s2.charAt(i) - 'a']++;
        if (i >= k) have[s2.charAt(i - k) - 'a']--;
        if (Arrays.equals(need, have)) return true;
    }
    return false;
}

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();
    if (s.length() < p.length()) return result;

    int[] pFreq = new int[26];
    int[] wFreq = new int[26];
    for (char c : p.toCharArray()) pFreq[c - 'a']++;

    int k = p.length();
    for (int i = 0; i < s.length(); i++) {
        wFreq[s.charAt(i) - 'a']++;
        if (i >= k) wFreq[s.charAt(i - k) - 'a']--;
        if (Arrays.equals(pFreq, wFreq)) result.add(i - k + 1);
    }
    return result;
}

// hash(s) = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
// Rolling: hash(window) = (hash(prev) - s[i-k]*31^(k-1)) * 31 + s[i]