Find the first non-repeating character in a string.

Find the first character that appears only once in a string, in two passes with a count array or LinkedHashMap, with complexity and edge cases.

0 0
Read Time:1 Minute, 31 Second

For “swiss” the answer is “w”: “s” repeats, “w” appears once and comes before “i”. The trick is that you need counts for the whole string before you can decide, so it takes two passes.

Two passes with a count array

static char firstUnique(String s) {
    int[] count = new int[256];          // extended ASCII
    for (char c : s.toCharArray()) count[c]++;
    for (char c : s.toCharArray()) {
        if (count[c] == 1) return c;
    }
    return '\0';                         // none found
}

First pass counts, second pass walks the string in its original order and returns the first character with count 1. Time O(n), space O(1) for a fixed alphabet. Walk the string in the second pass, not the count array, or you get the alphabetically first unique character instead.

LinkedHashMap version (any character set)

static Character firstUniqueMap(String s) {
    Map<Character, Integer> m = new LinkedHashMap<>();
    for (char c : s.toCharArray()) m.merge(c, 1, Integer::sum);
    for (Map.Entry<Character, Integer> e : m.entrySet())
        if (e.getValue() == 1) return e.getKey();
    return null;
}

LinkedHashMap keeps insertion order, so the second loop can go over the map instead of the string.

Edge cases

  • Empty string, or every character repeats (“aabb”): return a clear “not found” value and say what it is.
  • Case: is “A” the same as “a”? Ask.
  • Spaces and punctuation: count them or skip them?

Follow-ups

  • Return the index instead of the character.
  • Do it for a stream of characters, answering after each new character (keep a queue of candidates plus counts).
  • Find the first repeating character instead.

This answer was written by Debugger’s Space as practice material. It is asked in most Indian IT services interviews (TCS, Infosys, Wipro, HCLTech, Tech Mahindra, LTIMindtree, Accenture, Cognizant, Capgemini, IBM). See each company’s hiring steps and practice questions on Debugger’s Space.

Previous post Check whether two strings are anagrams.
Next post Explain the four pillars of OOP with a real example from your project.
Subscribe
Notify of
guest

0 Comments
Oldest
Newest Most Voted
Close
0
Would love your thoughts, please comment.x
()
x