Frequency Counting

One of the most common operations in string manipulation is counting how many times each character appears. While a HashMap<Character, Integer> is the general-purpose tool for this, string problems often have a constraint that allows for a much faster optimization.

1. The optimization: int[26]

If a problem states “the string consists of lowercase English letters,” you don’t need the overhead of a HashMap. You can use a simple integer array of size 26.

  • HashMap: High overhead (hashing function, collision handling, object wrappers).
  • Array: Instant access (index = char - 'a'), continuous memory, no overhead.

Code Comparison

Using HashMap (Slower):

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

Using Array (Faster):

int[] count = new int[26];
for (char c : s.toCharArray()) {
  count[c - 'a']++;
}

2. Problem: Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Visualization: Frequency Balance

We can increment counts for s and decrement for t. If they are anagrams, the final array should be all zeros.

Status: Idle

Implementation

public boolean isAnagram(String s, String t) {
  if (s.length() != t.length()) return false;

  int[] count = new int[26];

  for (int i = 0; i < s.length(); i++) {
    count[s.charAt(i) - 'a']++;
    count[t.charAt(i) - 'a']--;
  }

  for (int c : count) {
    if (c != 0) return false;
  }
  return true;
}

3. Problem: Group Anagrams

Given an array of strings strs, group the anagrams together.

Example:

  • Input: ["eat","tea","tan","ate","nat","bat"]
  • Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Strategy

Two strings are anagrams if and only if their sorted character counts are identical. We can use this character count (or a sorted version of the string) as the Key in a HashMap.

public List<List<String>> groupAnagrams(String[] strs) {
  if (strs == null || strs.length == 0) return new ArrayList<>();

  Map<String, List<String>> map = new HashMap<>();

  for (String s : strs) {
    // Create a unique key for each anagram group
    char[] ca = s.toCharArray();
    Arrays.sort(ca);
    String key = String.valueOf(ca);

    if (!map.containsKey(key)) {
      map.put(key, new ArrayList<>());
    }
    map.get(key).add(s);
  }

  return new ArrayList<>(map.values());
}

[!TIP] Sorting takes O(K log K) where K is the length of the string. The total complexity is O(N * K log K). Alternatively, you can create a key string like "1#0#2#...#0" representing the counts of a-z, which takes O(K) per string, improving total complexity to O(N * K).

Practice Problems

  1. First Unique Character in a String (Easy)
  2. Sort Characters By Frequency (Medium)
  3. Group Shifted Strings (Medium)

4. Deep Dive Strategy Lab: Frequency Counting

Intuition Through Analogy

Think of this chapter like searching text in a large log stream. The goal is not to memorize a fixed trick, but to repeatedly answer:

  1. What is the bottleneck?
  2. Which constraint dominates (time, memory, latency, correctness)?
  3. Which representation makes the bottleneck easier to eliminate?