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;
 }

Answer 2

My solution using a map of records.... Requires Java 14 or greater and enabling preview features. Seems a little verbose, but basically what the code below does is walk through the array of characters in the inputted String and create a record {character, index, count}. Then, it puts the created record on the map. Since put returns the previous value of that key, the code then "merges" the two records and replaces the entry with a new record that keeps the character and lower index and increments the higher count by one.

Lastly, it uses a stream to filter all entries in the map to only those that have a count of 1 and then returns the entry with the lowest index.

When inputting "loveleetcode" the code prints out the entry with the lowest index that has a count of 1:

v=CharacterCount[character=v, index=2, count=1]

Keep in mind that the record doesn't really need the character (since the key is the character). All you need in the record is the lowest index for that character and the count.

---

import java.util.Comparator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;

public class FirstUniqueCharacterDemo {
    
    public static void main (String[] args) {
//      String input1 = "leetcode"; // return 0
        String input1 = "loveleetcode"; // return 2

        Map<Character, CharacterCount> charMap = new LinkedHashMap<>();
        
        for (int i = 0; i < input1.length(); i++) {
            
            char c = input1.charAt(i);

            CharacterCount current = new CharacterCount(c, i, 1); // records are immutable
            CharacterCount previous = charMap.put(c, current);
            if(previous != null) {
                current = current.merge(previous); // combine records (add 1 to count and keep lower index)
                charMap.replace(c, current);
            }
        }

        Entry<Character, CharacterCount> lowestIndex = charMap.entrySet().stream()
            .filter(recordsWithOneEntry -> recordsWithOneEntry.getValue().count() == 1)
            .min(Map.Entry.comparingByValue(Comparator.comparingInt(CharacterCount::index))).orElse(null); // This will return either the CharacterCount record or null if none are found with a count of 1.
        
        System.out.println(lowestIndex);
        
    }

    public static record CharacterCount(char character, int index, int count) {
        public boolean isIndexGreater(int index) {
            return this.index > index;
        }
        
        public CharacterCount merge(CharacterCount cc) {
            int index = (isIndexGreater(cc.index()) ? cc.index : this.index);
            int count = this.count() > cc.count ? this.count() + 1 : cc.count() + 1;
            char c = this.character();
            return new CharacterCount(c, index, count);
        }
    }
}

Answer 3

separate the characters in two groups existing once or multiple times
(we don't need to count the characters)

firstNonRepeatingChar( "aaabcccddeggf" );
get the list List<Integer> uniques [3, 9, 12]
get the first element from uniques 3

public int firstNonRepeatingChar( String s ) {
  List<Integer> uniques = IntStream.range( 0, s.length() ).boxed().collect(
    partitioningBy(i -> s.indexOf(s.charAt( i ),
      s.indexOf(s.charAt( i )) + 1) == -1)).get( true );  // [3, 9, 12]
  return( uniques.isEmpty() ? -1 : uniques.get( 0 ) );    // 3
}

stopping with limit( 1 ) after finding the character of interest
a further simplification that aran's tip picks up on
this stream consists of only that one matching index, if there is any

public int firstNonRepeatingChar( String s ) {
  return( IntStream.range( 0, s.length() ).dropWhile( i -> s.indexOf(s.charAt( i ),
    s.indexOf(s.charAt( i )) + 1) > -1).limit( 1 ).findFirst().orElse( -1 ) );  // 3
}

Answer 4

You have 2 somewhat obvious options, that retains the spirit of using a LinkedHashMap :

1. you currently map the letter to the # of times it occurs. But that is not actually important; all you need to know is if the letter is unique (you don't need the count, you just need 'if I had the count, would it be 1?', which is considerably less information), and you need to know the position that it occurred at.

So why not map the character to the position instead of the count? Then, if you hit the same character again, you need to put something in the map to ensure you know it's no good (you can't remove it, because then a third occurrence would add it again, and would mean you give the wrong answer for input aaabc. Perhaps set it to -1 or some other value that means: This is not the answer you want).

2. Keep you code, but just loop through the string one more time, and find the index. Or just use String's indexOf method which does just that. This lets you turn e.g. the letter 'b' into the position in the string where the first 'b' occurs.

Answer 5

You can use String#indexOf method, that returns the index within this string of the first occurrence of the specified substring.

public static void main(String[] args) {
    String str1 = "leetcode";
    String str2 = "loveleetcode";
    String str3 = "aabbcc";

    String l1 = firstNonRepeatingString(str1);
    String l2 = firstNonRepeatingString(str2);
    String l3 = firstNonRepeatingString(str3);

    System.out.println(str1.indexOf(l1)); // 0
    System.out.println(str2.indexOf(l2)); // 2
    System.out.println(str3.indexOf(l3)); // -1
}

public static String firstNonRepeatingString(String str) {
    return Arrays
            // split string into an array of
            // substrings, i.e. characters,
            // Stream<String>
            .stream(str.split(""))
            // collect to map and count the number of repetitions
            .collect(Collectors.toMap(
                    s -> s, c -> 1, Integer::sum, LinkedHashMap::new))
            // iterate over entry set of this map
            // Stream<Map.Entry<String,Integer>>
            .entrySet().stream()
            // filter letters without repetitions
            .filter(entry -> entry.getValue() == 1)
            // take letter
            .map(Map.Entry::getKey)
            // first one
            .findFirst()
            // or a null character if
            // there are no such letters
            .orElse("\u0000");
}

---

^{See also: Java streams: groupingBy and flatMapping keys}