java - 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

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