First Unique Character in a String - Leet Code Solution

Problem Statement

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

Example

s = "leetcode"
return 0.

s = "loveleetcode"
return 2.

Note: You may assume the string contains only lowercase English letters.

Solution Brute Force

Lets take a look at the simple solution.

• Have two loops. first will iterate till length of string
• in second loop, iterate from beginning to end.
• And check if the character is found anywhere
• We can keep track of duplicate found by a boolean flag
• And if during our inner loop, if we found that character is not found. This is our answer

Code

public int firstUniqChar_bruteforce(String s) {
   for (int i=0; i<s.length(); i++) {
      boolean unique = true;
      for (int j=0; j<s.length(); j++) {
         if (i != j && s.charAt(i) == s.charAt(j)) {
            unique = false;
            break;
         }
      }
      
      if (unique) {
         return i;
      }
   }
   
   return -1;
}

Complexity

Its O(n^2)

Another Solution using a HashMap

• Iterate over string, and keep track of count of each character
• Maintain a HashMap<Character, Integer>
• Now, iterate over string again
• For each character, lookup in our HashMap
• If the count of that character is only 1, this is our answer
• Since, 1 means this character is in the string only 1 times.

Code

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

Complexity

Its O(n)