Java Solution for First Unique Character in a string using HashMap


  • 0
    A

    Approach #1 using Two-pass hash table

    Intuition

    Check all the characters in the string one by one and insert in HashMap with character as the key and index as the value. If a key repeats, set its value to -1.

    Algorithm

    Suppose we have a function intUniqChar(String S) . It returns the first unique character index.

    • Convert the string to char array and add all the characters to LinkedHashMap (to maintain the order).key is the character and value is the index.
      If a key already exists set its value to -1.
    • Add all the values to a LinkedList to maintain the order.
    • Find the first element from the list whose value is not equal to -1.
    • That value will be the index of first unique character in the string

    Java

    import java.util.Optional;
    class Solution {
        public int firstUniqChar(String s) {
            if (s.isEmpty())
                return -1;
            char[] charArray = s.toCharArray();
            Map<Character, Integer> map = new LinkedHashMap<>();
            // Adding the characters to a LinkedHashMap
            for (int i = 0; i < charArray.length; i++)
            {
               if(!map.containsKey(charArray[i])) 
               {
                   map.put(charArray[i],i);
               }
                else
                {
                    map.put(charArray[i],-1);
                }
            }
            List<Integer> values = new LinkedList<>();
            // Adding all the values in map to a LinkedList.
            values.addAll(map.values());
            // filtering the -1 indices and returning the first index.
            Optional<Integer> output = values.stream()
                    .filter(x -> !x.equals(-1)).findFirst();
            if(output.isPresent())
                return output.get();
            else return -1;
            
        }
    }
    

    Complexity Analysis

    • Time complexity : O(n)

    To verify if characters have duplicates, we need to read each character exactly once and it will lead to linear complexity which is O(n)

    • Space complexity : O(2m) (m <= lengthOfString)
      Since we insert all the unique characters only once in the HashMap which is m and also add all the values to LinkedList which is again m.
      So the space complexity is O(2m).

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.