The O(n) Club: Sort Characters By Frequency — and Stop Overengineering It

The O(n) Club: Sort Characters By Frequency — and Stop Overengineering It

⚡ TL;DR

Your job: shuffle the string so that characters with the highest frequency get to party up front—grouped and in descending order. No stacks, no heartbreak. Here’s Java at its least dramatic:

// Simple, no-fuss Java
String s = "tree";
Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) freq.put(c, freq.getOrDefault(c, 0) + 1);
List<Character> chars = new ArrayList<>(freq.keySet());
chars.sort((a, b) -> freq.get(b) - freq.get(a));
StringBuilder sb = new StringBuilder();
for (char c : chars) for (int i = 0; i < freq.get(c); i++) sb.append(c);
System.out.println(sb.toString()); // 'eert' or 'eetr'

🧠 How Devs Usually Mess This Up

🔍 What’s Actually Going On

Think of it like a nerdy party: the regulars (most frequent letters) grab the snack table. It doesn’t matter if e or t gets there first—only that all ‘e’s group together and all ‘t’s do too. No mixing, no food fights.

So you just:

• Count each character. (HashMap. Old-fashioned. Reliable.)
• Sort keys by frequency. The cool kid’s shortcut.
• Repeat each character as many times as it earned an invite. No more, no less.

🛠️ PseudoCode

• Count each character:

  for (char c : s.toCharArray())
      freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
  

  — HashMap does the heavy lifting.
• Sort by frequency:

  List<Character> chars = new ArrayList<>(freqMap.keySet());
  chars.sort((a, b) -> freqMap.get(b) - freqMap.get(a));
  

  — Descending. The MVPs lead the parade.
• Build the result:

  StringBuilder sb = new StringBuilder();
  for (char c : chars)
      for (int i = 0; i < freqMap.get(c); i++)
          sb.append(c);
  return sb.toString();
  

  — Repeat, append, done. No performance nightmares.

💻 The Code

public String frequencySort(String s) {
    Map<Character, Integer> freq = new HashMap<>();
    for (char c : s.toCharArray()) {
        freq.put(c, freq.getOrDefault(c, 0) + 1);
    }
    List<Character> chars = new ArrayList<>(freq.keySet());
    chars.sort((a, b) -> freq.get(b) - freq.get(a));
    StringBuilder sb = new StringBuilder();
    for (char c : chars) {
        for (int i = 0; i < freq.get(c); i++) {
            sb.append(c);
        }
    }
    return sb.toString();
}

⚠️ Pitfalls, Traps & Runtime Smacks

• If the result ends up with groups interleaving—like “cacaca” for “cccaaa”—something went wrong. Each gang hangs together.
• Single letter input? Just return it. Not every day is a group activity.
• Ties between groups? Any internal order is fine; your interviewer won’t care as long as you don’t split characters apart.
• Performance: Counting is O(n), sorting is O(k log k) where k = unique chars—usually tiny. You’re not sorting Unicode’s library here.
• Memory: Just a map and a list for the unique letters. If you’re running out of RAM, maybe close some browser tabs?

🧠 Interviewer Brain-Tattoo

“If you needed a stack, you probably misread the problem—or crave pain. Count, sort, group, and maybe get a snack.”