LeetCode 387 - First Unique Character in a String

https://leetcode.com/problems/first-unique-character-in-a-string/

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.

和原题不同的是⾯面试官要求返回字符，以及unique char不存在的情况怎么处理。

X. One Pass -  LinkedHashMap
https://leetcode.com/problems/first-unique-character-in-a-string/discuss/86511/Java-One-Pass-Solution-with-LinkedHashMap

LinkedHashMap will not be the fastest answer for this question because the input characters are just from 'a' to 'z', but in other situations it might be faster than two pass solutions. I post this just for inspiration.

public int firstUniqChar(String s) {
        Map<Character, Integer> map = new LinkedHashMap<>();
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            if (set.contains(s.charAt(i))) {
                if (map.get(s.charAt(i)) != null) {
                    map.remove(s.charAt(i));
                }
            } else {
                map.put(s.charAt(i), i);
                set.add(s.charAt(i));
            }
        }
        return map.size() == 0 ? -1 : map.entrySet().iterator().next().getValue();
    }

X. Two passes
https://leetcode.com/articles/first-unique-character-in-a-string/

  public int firstUniqChar(String s) {

    HashMap<Character, Integer> count = new HashMap<Character, Integer>();

    int n = s.length();

    // build hash map : character and how often it appears

    for (int i = 0; i < n; i++) {

      char c = s.charAt(i);

      count.put(c, count.getOrDefault(c, 0) + 1);

    }

    // find the index

    for (int i = 0; i < n; i++) {

      if (count.get(s.charAt(i)) == 1)

        return i;

    }

    return -1;

  }

https://leetcode.com/problems/first-unique-character-in-a-string/discuss/86348/Java-7-lines-solution-29ms

My solution is pretty straightforward. It takes O(n) and goes through the string twice:

1. Get the frequency of each character.
2. Get the first character that has a frequency of one.

Actually the code below passes all the cases. However, according to @xietao0221, we could change the size of the frequency array to 256 to store other kinds of characters. Thanks for all the other comments and suggestions. Fight on!

    public int firstUniqChar(String s) {
        int freq [] = new int[26];
        for(int i = 0; i < s.length(); i ++)
            freq [s.charAt(i) - 'a'] ++;
        for(int i = 0; i < s.length(); i ++)
            if(freq [s.charAt(i) - 'a'] == 1)
                return i;
        return -1;
    }

X. https://leetcode.com/problems/first-unique-character-in-a-string/discuss/86340/Java-two-pointers-(slow-and-fast)-solution-(18-ms)

The idea is to use a slow pointer to point to the current unique character and a fast pointer to scan the string. The fast pointer not only just add the count of the character. Meanwhile, when fast pointer finds the identical character of the character at the current slow pointer, we move the slow pointer to the next unique character or not visitedcharacter. (20 ms)

Is the time complexity O(n^2) ?

public class Solution {
    public int firstUniqChar(String s) {
        if (s==null || s.length()==0) return -1;
        int len = s.length();
        if (len==1) return 0;
        char[] cc = s.toCharArray();
        int slow =0, fast=1;
        int[] count = new int[256];
        count[cc[slow]]++;
        while (fast < len) {
            count[cc[fast]]++;
            // if slow pointer is not a unique character anymore, move to the next unique one
            while (slow < len && count[cc[slow]] > 1) slow++;  
            if (slow >= len) return -1; // no unique character exist
            if (count[cc[slow]]==0) { // not yet visited by the fast pointer
                count[cc[slow]]++; 
                fast=slow; // reset the fast pointer
            }
            fast++;
        }
        return slow;
    }