Topic 26 of 30 · Beginner
Find the first unique Unicode code point
Return the numeric code point of the first non-repeated code point, or -1 if absent.
BasicEntry level · 0–1 yearsHashing
Java 17+; compile each complete program as Main.java.
Problem statement
Return the numeric code point of the first non-repeated code point, or -1 if absent.
Locate a unique marker in a character stream.
Input: Non-null String.
Output: Code point integer or -1.
- Case sensitive.
- Preserve original encounter order.
Sample 1
Input: aabcc Output: 98
b is the first unique code point.
Sample 2
Input: aabb Output: -1
All code points repeat.
Brute-force solution
For each code point count equal occurrences by scanning the complete string.
O(n) expected.
import java.util.*;
class Main {
static int firstUnique(String s){Map<Integer,Integer> count=new HashMap<>();s.codePoints().forEach(c->count.merge(c,1,Integer::sum));return s.codePoints().filter(c->count.get(c)==1).findFirst().orElse(-1);}
public static void main(String[] args) throws Exception {
System.out.println(firstUnique("aabcc"));
if(firstUnique("aabcc")!=98 || firstUnique("aabb")!=-1)throw new AssertionError();
}
}
Optimized solution
Count frequencies once, then scan the original encounter order for count one.
- Count with a map.
- Scan original order.
- Return first count-one code point.
import java.util.*;
class Main {
static int firstUnique(String s){Map<Integer,Integer> count=new HashMap<>();s.codePoints().forEach(c->count.merge(c,1,Integer::sum));return s.codePoints().filter(c->count.get(c)==1).findFirst().orElse(-1);}
public static void main(String[] args) throws Exception {
System.out.println(firstUnique("aabcc"));
if(firstUnique("aabcc")!=98 || firstUnique("aabb")!=-1)throw new AssertionError();
}
}
Complexity analysis
Time: O(n) expected.
Auxiliary space: O(u) distinct code points.
Test cases
- Empty.
- Supplementary characters.
- No unique.
The supplied main asserts a unique and no-unique case; also assert firstUnique("")==-1.Common mistakes
- Iterating HashMap keys as if ordered.
- Counting char halves instead of code points.
Key takeaways
- Frequency and order are separate.
- Do a second encounter-order pass.
- Use explicit no-match sentinel.
Follow-up challenges
- How would you return a UTF-16 index instead?
- How would online streaming change state?