The O(n) Club: Find Common Characters — Where Duplicate Letters Are Finally Invited

The O(n) Club: Find Common Characters — Where Duplicate Letters Are Finally Invited

⚡ TL;DR

Want every letter that appears in all strings, with each duplicate treated like it matters (because it does)? Think frequency, not sets. Count every character per string, keep the lowest count for each letter, and only those lucky ones go home with a prize. Java demo below:

// Given String[] words, return List<String> of common chars (incl. duplicates)
int[] min = new int[26];
Arrays.fill(min, Integer.MAX_VALUE);
for (String word : words) {
    int[] freq = new int[26];
    for (char c : word.toCharArray()) freq[c - 'a']++;
    for (int i = 0; i < 26; i++) min[i] = Math.min(min[i], freq[i]);
}
List<String> result = new ArrayList<>();
for (int i = 0; i < 26; i++)
  for (int j = 0; j < min[i]; j++)
    result.add("" + (char)(i + 'a'));

🧠 How Devs Usually Mess This Up

See the word “common” and suddenly everyone’s unionizing sets. You make your sets, do intersections, and (whoops) wave goodbye to duplicates. If the answer wants triple-“l”, your set gives you… one. Sad trombone. People also try to brute-force-compare each character between every pair of strings, inventing the world’s slowest spellchecker. But the universe does not reward O(n³) solutions unless your interviewer hates their own laptop.

🔍 What’s Actually Going On

Picture your code as a neurotic chef: every letter gets chopped up, but only the scarcest ingredient (minimum count) for each matters. One word out of paprika? Paprika’s gone from the recipe. “Common” with duplicate means we count every letter in every word, then take as many as the smallest pile. It’s like preparing team sandwiches and only using what’s survived your friends’ snacking.

🛠️ PseudoCode

• Initialize an array minCounts of 26 (for a–z), set all to infinity (or at least Integer.MAX_VALUE).
• Loop through each word:
  • Count every letter’s frequency in a new 26-size array.
  • Update minCounts for each letter: minCounts[i] = min(minCounts[i], freq[i]).
• For each letter A–Z, if minCounts[i] > 0, add it that many times to the result list.
• Return that list. Cue applause.

💻 The Code

import java.util.*;
 public class FindCommonChars {
    public List<String> commonChars(String[] words) {
        int[] minCounts = new int[26];
        Arrays.fill(minCounts, Integer.MAX_VALUE);
        for (String word : words) {
            int[] freq = new int[26];
            for (char c : word.toCharArray()) freq[c - 'a']++;
            for (int i = 0; i < 26; i++) minCounts[i] = Math.min(minCounts[i], freq[i]);
        }
        List<String> res = new ArrayList<>();
        for (int i = 0; i < 26; i++)
            for (int j = 0; j < minCounts[i]; j++)
                res.add(String.valueOf((char)(i + 'a')));
        return res;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Sets betray you: If you use a Set or intersect without tracking counts, duplicates straight-up vanish. Don’t do it.
• Missing characters: If any word skips a letter, it gets zero appearances. No participation trophies here.
• Edge case: Yes, input can include words like “zzz”, so don’t hardcode for vowels or something weird.
• Complexity: O(N * L), where N = number of words, L = max word length. Space? Only 26. Your RAM won’t even blink.

🧠 Interviewer Brain-Tattoo

If you hear “common with duplicates,” reach for your counter, not your set. Count like you’re being charged per loop (because, really, you are).