[Java Solution] O(n) w/ Streams and LinkedHashMap


  • 0
    P

    In my solution I decided to use a LinkedHashMap, because this data structure ensures that when I insert the chars in the hashmap, the order of insertion will be maintained.
    This guarantees that when I iterate over the chars, they will be ordered by the order of appearance in the string.

    This way, I only need to find the first element, whose count is exactly 1, since that means they have appeared only once in the String.

    I've used Streams because they allow us to use lazy evaluation within Java. With Lazy evaluation I evaluate as few elements as possible, until I find the value I was looking for. In my case, I just want to find the first key of the hash map whose counting is equal to 1. Java will only parse enough keys until it finds the first one with counts == 1, thus preventing from iterating over the whole key set.

    public int firstUniqChar(String s) {
         LinkedHashMap<Integer, Integer> charCounts = new LinkedHashMap<>();
    
        // Inserts the count of each char by the order they appear in s
        s.chars().forEachOrdered(ch -> charCounts.put(ch, charCounts.getOrDefault(ch, 0) + 1));
    
        // Retrieves the first char whose count was 1 (filter is a lazy operation :) )
        return s.indexOf(s.chars().filter(count -> charCounts.get(count) == 1).findFirst().orElse(-1));
    }

Log in to reply
 

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