LeetCode #387 First Unique Character in a String Solution & Explanation

LeetCode Problem

Given a string sfind the first non-repeating character in it and return its index. If it does not exist, return -1.

LeetCode #387 Examples
LeetCode #387 Constraints

Solution

C# Solution

Solution1 – Dictionary & HashSet

public class Solution {
    public int FirstUniqChar(string s) {
        Dictionary<char,int> dict =   new Dictionary<char,int>();
        HashSet<char> hSet = new HashSet<char>();
        
        for(int i = 0; i<s.Length;i++)
        {
            char c = s[i];
            
            if(hSet.Contains(c))
            {
                continue;
            }
                
            
            if (!dict.ContainsKey(c))
            {
                dict.Add(c, i);
            }
            else
            {
                dict.Remove(c);
                hSet.Add(c);
            }
        }
        
        if(dict.Count == 0)
        {
            return -1;
        }
        
         return dict.MinBy(k => k.Value).Value;
    }
}

We use Dictionary to store character and index ( need it to find the first character ) .

And a HashSet to check if the character had been seen or not.

Runtime : 94ms、117ms、73ms

Time Complexity : O(n)

Solution2 – ASCII iteration ( *1 )

public class Solution {
    public int FirstUniqChar(string s) {
        
        int min = Int32.MaxValue;
        
        for (char c = 'a'; c <= 'z'; c++)
        {
            int tmp = s.IndexOf(c);
            if(tmp!=-1 && tmp == s.LastIndexOf(c))
            {
                min = tmp<min ? tmp : min;
            }
        } 
        min = min == Int32.MaxValue ? -1 : min;
            
        return min;
    }
}

In the second solution, we enumerate the alphabet ( 26 times instead of solution1’s length of s times)

If IndexOf equals as LastIndexOf means that there are only one character in the word s.

Runtime : 96ms、79ms、83ms Faster than 90% ⬆️

Time Complexity : O(n)

Java Solution

Solution1

class Solution {
    public int firstUniqChar(String s) {
        Map<Character, Integer> dict = new HashMap<Character, Integer>();
        HashSet<Character> hSet  = new HashSet<Character>();
        
        for(int i = 0; i<s.length();i++)
        {
            char c = s.charAt(i);
            
            if(hSet.contains(c))
            {
                continue;
            } 
            
            if (!dict.containsKey(c))
            {
                dict.put(c, i);
            }
            else
            {
                dict.remove(c);
                hSet.add(c);
            }
        }
        
        if(dict.size() == 0)
        {
            return -1;
        }
        
        int min = Integer.MAX_VALUE;
        
        for (Integer value : dict.values()) {
            min = value<min ? value : min;
        }
        
        return min;
    }
}

Runtime : 21ms、16ms、17ms Faster than 70%

Solution2

class Solution {
    public int firstUniqChar(String s) {
        int min = Integer.MAX_VALUE;
        
        for (char c = 'a'; c <= 'z'; c++)
        {
            int tmp = s.indexOf(c);
            if(tmp!=-1 && tmp == s.lastIndexOf(c))
            {
                min = tmp<min ? tmp : min;
            }
        } 
        min = min == Integer.MAX_VALUE ? -1 : min;
            
        return min;
    }
}

Runtime : 2ms、2ms、1ms Faster than 99.66~100%

Python3 Solution

Solution1

from string import ascii_lowercase as alc

class Solution:
    def firstUniqChar(self, s: str) -> int:
        
        m = math.pow(10,5);     #min
        
        for c in alc:
            try:
                tmp = s.index(c)
                tmp2 = s.rindex(c)
            except: 
                continue;
                
            if tmp == tmp2:
                m = tmp if tmp<m else m
                
        return -1 if m == math.pow(10,5) else m

Runtime : 39ms、15ms、35ms Faster than 99.99~100%

JavaScript Solution

Solution1

/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function(s) {
    var min = 10**5;
    for (var i = 97; i <= 122; i++) {
        var c = String.fromCharCode(i);
        
        var tmp = s.indexOf(c);
        if(tmp!=-1 && tmp == s.lastIndexOf(c))
        {
            min = tmp<min ? tmp : min;
        }
    }
    
    min = min == 10**5 ? -1 : min;
    return min;
};

Runtime : 77ms、81ms、69ms


Submission Detail


Conclusion

🧡If my solution helps, that is my honor!

🧡You can support me by clicking some ad, Thanks a lot

If you got any problem about the explanation or you need other programming language solution, please feel free to let me know (either leave a comment or contact me by Messenger is ok!)

The problem link : First Unique Character in a String – LeetCode

Reference

Latest Post

Leave a Reply

Your email address will not be published. Required fields are marked *