[FIXED] Finding the first Non-repeating Character in the given string, not able to pass a few test cases due to Timeout

Issue

I'm working on a Problem from CodeSignal:

Given a String s consisting of the alphabet only, return the first non-repeated element. Otherwise, return '-'.

Example: input - s="abacabad", output - 'c'.

I came up with the following the code. It passes only 16/19 test cases. Is there a way to solve this problem in O(n) or O(1)?

My code:

public char solution(String s) {
    ArrayList<Character> hs = new ArrayList<>();
    
    for (char c:s.toCharArray()) {
        hs.add(c);
    }
    
    for (int j=0; j<s.length(); j++) {
        if ( 1 == Collections.frequency(hs, s.charAt(j))) {
            return s.charAt(j);
        }
    }
    
    return '_';
}

Solution

The minimal possible time complexity for this task is linear O(n), because we need to examine every character in the given string to find out whether a particular character is unique.

Your current solution runs in O(n^2) - Collections.frequency() iterates over all characters in the string and this iteration and this method is called for every character. That's basically a brute-force implementation.

We can generate a map Map<Character,Boolean>, which associates each character with a boolean value denoting whether it's repeated or not.

That would allow to avoid iterating over the given string multiple times.

Then we need to iterate over the key-set to find the first non-repeated character. As the Map implementation LinkedHashMap is used to ensure that returned non-repeated character would be the first encountered in the given string.

To update the Map I've used Java 8 method merge(), which expects three arguments: a key, a value, and a function responsible for merging the old value and the new one.

public char solution(String s) {
    Map<Character, Boolean> isNonRepeated = getMap(s);
    
    for (Map.Entry<Character, Boolean> entry: isNonRepeated.entrySet()) {
        if (entry.getValue()) {
            return entry.getKey();
        }
    }        
    
    return '_';
}

public Map<Character, Boolean> getMap(String s) {
    Map<Character, Boolean> isNonRepeated = new LinkedHashMap<>();
    
    for (int i = 0; i < s.length(); i++) {
        isNonRepeated.merge(s.charAt(i), true, (v1, v2) -> false);
    }
    return isNonRepeated;
}

In case if you're comfortable with streams, this problem can be addressed in one statement (the algorithm remains the same and time complexity would be linear as well):

public char solution(String s) {
    
    return s.chars()
        .mapToObj(c -> (char) c)
        .collect(Collectors.toMap( // creates intermediate Map<Character, Boolean>
            Function.identity(),   // key
            c -> true,             // value - first occurrence, character is considered to be non-repeated
            (v1, v2) -> false,     // resolving values, character is proved to be a duplicate
            LinkedHashMap::new
        ))
        .entrySet().stream()
        .filter(Map.Entry::getValue)
        .findFirst()
        .map(Map.Entry::getKey)
        .orElse('_');
}

Answered By - Alexander Ivanchenko
Answer Checked By - Robin (JavaFixing Admin)