First Non-Repeating Character

easy Strings

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

Best approachTime O(n)Space O(1)

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.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * 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)
  1. Why can't we decide in the first pass?