CodeSignal Interview – firstNotRepeatingCharacter

Problem

Given a string s consisting of small English letters, find and return the first instance of a non-repeating character in it. If there is no such character, return '_'.

Example

• For s = "abacabad", the output should be
  solution(s) = 'c'.There are 2 non-repeating characters in the string: 'c' and 'd'. Return c since it appears in the string first.
• For s = "abacabaabacaba", the output should be
  solution(s) = '_'.There are no characters in this string that do not repeat.

Solution

Idea

My idea is pretty simple. It similar to CodeSignal Interview – firstDuplicate.

• Build a mapping array with alphabet character as index. All elements’ value are 0.
• Loop through the input string.
  • If character appears the first time, mark it as 1 and add it to a result string.
  • If character appears the second time:
    • Remove all the same character in input string
    • Remove that character in result
• Return:
  • If result is empty, return _.
  • If result is not empty, return the first character.

Code

function solution(s) {
    let alphabet = 'abcdefghijklmnopqrstuvwxyz';
    let seen = {};
    let result = '';
    for (let i = 0; i < alphabet.length; i++) {
        seen[alphabet[i]] = 0;
    }
    
    while(s.length > 0) {
        let c = s[0];
        s = s.substring(1);
        if (seen[c] === 0) {
            seen[c] = 1;
            result += c;
            continue;
        }
        
        s = s.replace(c, '');
        result = result.replace(c, '');
    }
    
    return result === '' ? '_' : result[0];
}