First Unique Character in a String

Given a string, find the first non-repeating character in it and return its index. If it doesn't exist, return -1.

Approach1: HashMap

Tjis approach is very intuitive, we do a first pass of the characters of the string at hand and store their frequency in a map. We then do a second iteration over the string with the first character that we encounter with a frequency that is equal to 1 (unique), we return it's index.

class Solution:
    def firstUniqChar(self, s: str) -> int:
        mp = {}
        
        for c in s:
            if c not in mp:
                mp[c] = 1
            else:
                mp[c] = mp.get(c) + 1
                
        for i, c in enumerate(s):
            if mp.get(c) == 1:
                return i
        
        return -1

Time: O(n) Space: O(k) k = distinct characters

Approach1: HashMap2

This approach is the same as the one implemented above with the exception that we're using the list as HashMap to map the characters to their frequency.

class Solution:
    def firstUniqChar(self, s: str) -> int:
        lst = [0] * 128
        for c in s:
            lst[ord(c)] += 1
        
        for i, c in enumerate(s):
            if lst[ord(c)] == 1:
                return i
        
        return -1

Approach1: HashMap (Java )

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

Approach2: Ordered Dictionary

class Solution:
    def firstUniqChar(self, s: str) -> int:
        d = {}
        seen = set()
        
        for i, e in enumerate(s):
            if e not in seen:
                seen.add(e)
                d[e] = i
            elif e in d:
                del d[e]
        
        return -1 if len(d) == 0 else next(iter(d.values()))

The above approaches are good soulution however they can be improved since we're scanning the array twice. To prevent a second pass, we use a Set to validate whether or not a character has been seen before. If the Character is not in the Set, we add it to the Set as well as the Map otherwise we remove it from the map. Since our Items were being entered in order, the first item would be the first unque one.

Why the improvement ?

ex1: Take an example of DNA sequence: there could be millions of letters long with just 4 alphabet letter. What happened if the non-repeated letter is at the end of DNA sequence? We could dramatically increase our running time by scanning gthe array just once.

ex2: Let's say we have a trading platform, and we want the first non repeating orders. This due to some Buy Side Traders having made the efforts to render our algorithm less efficient by splitting large market orders into smaller sub-orders that arrive at the same time to all the exchanges. With a simple pass, we can improve the runtime of our algorithm as we would be analyzing that data stream as it comes in.

Time: O(n) Space: O(k) k = distinct characters

Approach2: Ordered Dictionary (Java Version)

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