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

CodePudding user response：

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('_');
}

CodePudding user response：

One technique would be a 2 pass solution using a frequency/count array for each character.

public static char firstNonRepeatingChar(String s) {
        int[] frequency = new int[26]; // this is O(1) space complexity because alphabet is finite of 26 letters
        
        /* First Pass - Fill our frequency array */
        for(int i = 0; i < s.length(); i  ) {
            frequency[s.charAt(i) - 'a']  ;
        }
        /* Second Pass - Look up our frequency array */
        for(int i = 0; i < s.length(); i  ) {
            if(frequency[s.charAt(i) - 'a'] == 1) {
                return s.charAt(i);
            }
        }
        /* Not Found */
        return '_';
    }

This solution is O(2n) -> O(n) and a space complexity of O(1) because we are using a finite set of the English alphabet (26 letters). This wouldn't work in other scenarios for non-English alphabets.