The O(n) Club: First Unique Character in a String—How to Outsmart a Classic Interview Trap

The O(n) Club: First Unique Character in a String—How to Outsmart a Classic Interview Trap

⚡ TL;DR

You want the index of the first non-repeating character in a string of lowercase letters. Not the character. Not a cryptic prophecy. Definitely not every unique letter. Brute force is O(n²) and will make your CPU cry. The grown-up way is O(n): count each char’s appearances, then stroll through the string and return the index of the lonely soul.

// Brute force—works, but will cost you interviewer eye contact
for (int i = 0; i < s.length(); i++) {
    boolean unique = true;
    for (int j = 0; j < s.length(); j++) {
        if (i != j && s.charAt(i) == s.charAt(j)) {
            unique = false;
            break;
        }
    }
    if (unique) return i;
}
return -1;

🧠 How Devs Usually Mess This Up

It’s like a bug magnet. Here’s what people try and why it lands in the fail bin:

• Returning the character, not the index. I get it—you want to be helpful. But the prompt is clear as Java coffee: “index.”
• Grabbing all unique characters— but we only care about the first one. Not every wallflower at the dance. Leave the rest to existential angst.
• Worrying about space for a hash map— But you only need to count 26 possibilities. Even a potato could fit that.
• Attempting a single-pass miracle— Sorry, no cheating here. You need the counts before deciding who’s unique.

🔍 What’s Actually Going On

Imagine a karaoke night where every singer shrieks their name as they step on stage. Your job? Spot the first solo act who doesn’t share a name with anyone else in the lineup. First, count how many times each name echoes through the speakers. Only then can you point, like a benevolent Simon Cowell, at the debut solo and say, “You. You’re special. Here’s your index!”

🛠️ PseudoCode

• First Pass: Count characters.
  • Use int[26] for the alphabet. For every c in s, do freq[c - 'a']++;
• Second Pass: Find the first unique.
  • Loop from start. If freq[s.charAt(i) - 'a'] == 1, return i.
• None found? Return -1. This is not a sign to quit programming.

💻 The Code

public int firstUniqChar(String s) {
    int[] freq = new int[26];
    for (int i = 0; i < s.length(); i++) {
        freq[s.charAt(i) - 'a']++;
    }
    for (int i = 0; i < s.length(); i++) {
        if (freq[s.charAt(i) - 'a'] == 1) {
            return i;
        }
    }
    return -1;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Returns -1?  If all letters repeat, -1 is the right answer. Debug your interviewer, not your code.
• Single-letter strings? Index 0—it’s the main character’s story and they know it.
• Oddball chars (🚀, “Z”, spaces)? The input should be lowercase a-z. Anything else could crash your party.
• Complexity: 2 passes: O(n). The array is O(1) because the English alphabet isn’t going to start taking on new members now.

🧠 Interviewer Brain-Tattoo

“Don’t let the word ‘unique’ fool you—this isn’t a dating site. Give me the first index or give me -1. Anything else is just emotional baggage.”