First Unique Character in a String

Problem

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.

Solution

Solution Using HashMap: O(n) time and O(n) space

public class Solution {
    public int firstUniqChar(String s) {
        if (s == null || s.length() == 0) return -1;
        Map<Character, Integer> map = new HashMap<>();
        for (char ch : s.toCharArray()) map.put(ch, map.getOrDefault(ch, 0) + 1);
        for (int i = 0; i < s.length(); i++) {
            if (map.get(s.charAt(i)) == 1) return i;
        }
        return -1;
    }
}

Optimal Space Solution Using Array: O(n) time and O(1) space

public class Solution {
    public int firstUniqChar(String s) {
        if (s == null || s.length() == 0) return -1;
        int[] freq = new int[26];
        for (char ch: s.toCharArray()) freq[ch - 'a']++;
        for (int i = 0; i < s.length(); i++) {
            if (freq[s.charAt(i) - 'a'] == 1) return i;
        }
        return -1;
    }
}

Analysis

The idea in these two solutions are similar
We store the character with their frequency in the given String
Then we loop the String and return the first character with frequency 1
Using the int[26] we optimize the space from O(n) to O(1), because the size of array is fixed