First Non-Repeating Character
Problem
Read one word (no spaces). Print the first character that appears exactly once. If every character repeats, print none.
Constraints
- 1 <= length <= 10^5, ASCII, no spaces
Examples
Input
swiss
Output
w
Solutions
Pass 1 counts all characters. Pass 2 finds the first character whose count is 1. We need two passes, because we must know the final counts before we decide.
/*
* Problem : Process one line of text.
* Input : One line of text.
* Output : The first unique character.
* Approach: Two passes.
* Time : O(n)
* Space : O(1)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static String solve(String s) {
// Step 1: Count every character. 256 places are enough for ASCII.
int[] counts = new int[256];
for (int i = 0; i < s.length(); i++) {
counts[s.charAt(i)]++;
}
// Step 2: Walk through the word again, in the original order.
for (int i = 0; i < s.length(); i++) {
// Step 3: The first character with the count 1 is the answer.
if (counts[s.charAt(i)] == 1) {
return String.valueOf(s.charAt(i));
}
}
return "none";
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.hasNextLine() ? scanner.nextLine() : "";
System.out.println(solve(s));
}
}
Hints (1)
- Why can't we decide in the first pass?