package buildingblock.table.alphabet.lc387_firstuniquecharacterinastring;

/**
 * Given a string, find the first non-repeating character in it and return it's index.
 * If it doesn't exist, return -1.
 * Examples:
 *  s = "leetcode". return 0.
 *  s = "loveleetcode", return 2.
 * Note: You may assume the string contain only lowercase letters.
 */
public class Solution {

    public int firstUniqChar(String s) {
        int[] letters = new int[26];
        for (char c : s.toCharArray()) {
            letters[c - 'a']++;
        }

        for (int i = 0; i < s.length(); i++) {
            if (letters[s.charAt(i) - 'a'] == 1) {
                return i;
            }
        }
        return -1;
    }

}

@@ -68,16 +68,65 @@
 tring;%0A%0A
+import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A * G
@@ -424,331 +424,1216 @@
     
-public int firstUniqChar(String s) %7B%0A        int%5B%5D letters = new int%5B26%5D;%0A        for (char c : s.toCharArray()) %7B%0A            letters%5Bc - 'a'%5D++;%0A        %7D%0A%0A        for (int i = 0; i %3C s.length(); i++) %7B%0A            if (letters%5Bs.charAt(i) - 'a'%5D == 1) %7B%0A                return i;%0A            %7D%0A        %7D%0A        return -1
+// Very straightforward and elegant O(N) time and O(1) space solution%0A    public int firstUniqChar(String s) %7B%0A        int%5B%5D freq = new int%5B26%5D;%0A        for (int i = 0; i %3C s.length(); i++) freq%5Bs.charAt(i) - 'a'%5D++;%0A        for (int i = 0; i %3C s.length(); i++) %7B%0A            if (freq%5Bs.charAt(i) - 'a'%5D == 1) return i;%0A        %7D%0A        return -1;%0A    %7D%0A%0A    public int firstUniqChar1(String s) %7B%0A        int%5B%5D letters = new int%5B26%5D;%0A        for (char c : s.toCharArray()) %7B%0A            letters%5Bc - 'a'%5D++;%0A        %7D%0A%0A        for (int i = 0; i %3C s.length(); i++) %7B%0A            if (letters%5Bs.charAt(i) - 'a'%5D == 1) %7B%0A                return i;%0A            %7D%0A        %7D%0A        return -1;%0A    %7D%0A%0A    // Not straightforward and waste space%0A    public int firstUniqChar21(String s) %7B%0A        if (s.isEmpty()) return -1;%0A%0A        Map%3CCharacter, Integer%3E idx = new HashMap%3C%3E();%0A        for (int i = 0; i %3C s.length(); i++) %7B%0A            char c = s.charAt(i);%0A            if (idx.containsKey(c)) idx.put(c, Integer.MAX_VALUE);%0A            else idx.put(c, i);%0A        %7D%0A%0A        int min = Integer.MAX_VALUE;%0A        for (int i : idx.values()) min = Math.min(min, i);%0A        return min == Integer.MAX_VALUE ? -1 : min
 ;%0A  

first unique character in a string