First Unique Character in a String

Given a string find the index of the first unique character (non repeating).

For example,

For the string “see” the output is 0 since the letter s is not repeated in the string

For the string “bbaaddavt” the output is 7 because the letter v is not repeated and is present in index 7.

Assumption:

The given word contains only lower case English alphabets

Try out the solution here:

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

Solution:

Convert the given string to a character array.

Then pass through each letter in the array twice.

During the first pass , create a frequency counter to store the number of times the character appears in the string.

You can use a map data structure or a primitive integer array (more efficient).

During the second pass check if the character frequency is one then return the index.

Here is the implementation using hash map:

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

Here is the implementation using an integer array:

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

Time complexity:

In both the cases we make two passes along the array.

So time complexity is O(n)

Space complexity:

In both the cases we use an extra data structure to store the frequency of English letters . As per assumption we have only lower case English letters to deal with . The total storage capacity is 26 and is a constant.

So space complexity is O(1)

That’s it!