First unique character in a string using LinkedHashMap

Question

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

Examples:

s = "leetcode"
return 0.

s = "loveleetcode"
return 2.

In my solution I can find the character itself but I am looking to get the index of the character! How would I change my code to get the index using LinkedHashMap? And thank you in advance.

public static void firstNonRepeatingString(String str) {
    LinkedHashMap<Character, Integer> lhm = new LinkedHashMap<>();
    char[] charArray = str.toCharArray();
    for (char character : charArray) {
        if (lhm.get(character) == null) {
            lhm.put(character, 1);
        } else {
            lhm.put(character, lhm.get(character) + 1);
        }
    }

    for (Map.Entry<Character, Integer> entry : lhm.entrySet())
        if (entry.getValue() == 1) {
            System.out.print(entry.getKey());
            break;
        }
}

firstNonRepeatingString("aaabcccddeggf"); 

This will print b, but I want to print 3.

Answer 1

HashSet

The set is only used to avoid computing again a character that's already been seen. The set doesn't need to respect insertion order, as its goal is just check if an element exists. For that, HashSet is a proper option.

StringUtils has some good utils indeed, one of them is counting the occurrences of a single char/string within the source string.

As you want the first character which is unique, if the element didn't exist in the set and countMatches returns 1, you got your result.

If no uniques are found, return -1 (for example) as representation that no uniques were found in the string.

public static int firstNonRepeatingCharIndex(String str) 
{
   HashSet<Character> dupSet = new HashSet<>();   //duplicates list
   for(char c : str.toCharArray()) 
   {
      if (dupSet.contains(c))
          continue;
      if (StringUtils.countMatches(str, c) == 1)
          return str.indexOf(c);
      dupSet.add(c);
   }
   return -1;
}

This avoids:

• Useless iteration through all characters, after the result was found.
• Useless proccess of characters already seen.
• Useless map creation and its related operations, such as aggregations.

---

HashSet + LinkedHashSet

For this specific problem, this shouldn't be required, but just in case you want to know which are the uniques and their order, so you want to iterate until the end, using two Sets could be an option.

public static int firstNonRepeatingCharIndex(String str) 
{
   LinkedHashSet<Character> lSet = new LinkedHashSet<>();
   HashSet<Character> dupSet = new HashSet<>();   //duplicates list

   for(char character : str.toCharArray()) 
   {
      if (dupSet.contains(character))  //exists in duplicates, continue
          continue;         
      if (lSet.contains(character))   //exists in the linkedSet, add to duplicates
          dupSet.add(character);          
      else
          lSet.add(character);        //first time seen, add to linkedSet
   } 

   lSet.removeAll(dupSet);          //remove all duplicates 
   if (lSet.isEmpty())
        return -1;

   return str.indexOf(lSet.iterator().next());  
}

---

LinkedHashMap

Only if the complete map is required, for getting stats, or whatever.

Note there's no need to add/modify the entries. We directly set the number of occurrences if the key is not in the map.

public static int firstNonRepeatingCharIndex(String str) 
{
  LinkedHashMap <Character , Integer> lhm = new LinkedHashMap<>();
  int c = 0, index = -1;
  for(char character : str.toCharArray()) 
  {
     if (lhm.get(character) == null)
     {
        int oc = StringUtils.countMatches(str,character);
        if (oc==1 && index<0)
           index = c;           //will only bet set once
        lhm.put(character, oc);
      }            
      if (index<0)     
        c++;                   //no need for this after index is found
   } 
   //showStatsOfMap(lhm); ?
   return index;
}

---

If you don't need the map's result at all (which makes you wonder why there's a map here)

public static int firstNonRepeatingCharIndex(String str) 
{
   LinkedHashMap <Character , Integer> lhm = new LinkedHashMap<>();
   int c = 0;
   for(char character : str.toCharArray()) 
   {
      if (lhm.get(character)==null)
      {
          int oc = StringUtils.countMatches(str,character);
          if (oc == 1)
             return c;
          lhm.put(character, oc);
      }
       c++;
   }    
    //sendNonUniqueMap(lhm); //??? just to make use of it...
    return -1;
 }