package com.freetymekiyan.algorithms.other;

/**
 * Given a string, find the first unique character.
 * <p>
 * Company: Facebook
 */
public class FirstUniqueCharacter {

    /**
     * Hash table.
     * Save count of each character in a map.
     * Then find the first one that has count as 1.
     */
    public char findFirstUnique(String s) {
        if (s == null || s.isEmpty()) {
            throw new IllegalArgumentException("Input string must exist or be non-empty.");
        }
        int[] counts = new int[128];
        char[] chs = s.toCharArray();
        for (char c : chs) {
            counts[c]++;
        }
        for (char c : chs) {
            if (counts[c] == 1) {
                return c;
            }
        }
        throw new IllegalStateException("Input string doesn't have a unique character.");
    }
}
@@ -288,16 +288,215 @@
 t as 1.%0A
+     * If the count array stores count and index, another linear scan won't be needed.%0A     * Just scan the count array and find the character that has:%0A     * 1. count = 1.%0A     * 2. Minimum index.%0A
      */%0A
@@ -694,16 +694,18 @@
    int%5B%5D
+%5B%5D
  counts 
@@ -718,11 +718,14 @@
 int%5B
-128
+256%5D%5B2
 %5D;%0A 
@@ -770,36 +770,54 @@
        for (
-char c : chs
+int i = 0; i %3C chs.length; i++
 ) %7B%0A        
@@ -828,16 +828,24 @@
 counts%5Bc
+hs%5Bi%5D%5D%5B0
 %5D++;%0A   
@@ -841,33 +841,109 @@
 %5D%5B0%5D++;%0A        
-%7D
+    counts%5Bchs%5Bi%5D%5D%5B1%5D = i;%0A        %7D%0A%0A        int minIdx = Integer.MAX_VALUE;
 %0A        for (ch
@@ -944,19 +944,23 @@
 or (
-char
+int%5B%5D
  c : c
-h
+ount
 s) %7B
@@ -981,21 +981,33 @@
 f (c
-ounts%5Bc%5D == 1
+%5B0%5D == 1 && c%5B1%5D %3C minIdx
 ) %7B%0A
@@ -1026,16 +1026,21 @@
     
-return c
+minIdx = c%5B1%5D
 ;%0A  
@@ -1053,32 +1053,77 @@
     %7D%0A        %7D%0A
+        if (minIdx == Integer.MAX_VALUE)%0A    
         throw ne
@@ -1192,19 +1192,47 @@
 aracter.%22);%0A
+        return chs%5BminIdx%5D;%0A
     %7D%0A%7D

optimize First Unique Character with one-pass