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.

Input/Output

• [execution time limit] 3 seconds (java)

• [memory limit] 1 GB

• [input] string s

  A string that contains only lowercase English letters.

  Guaranteed constraints:

  1 ≤ s.length ≤ 105.

• [output] char

  The first non-repeating character in s, or '_' if there are no characters that do not repeat.

풀이

char solution(String s) {
    // char : count
    // LinkedHashMap  이므로 순서 보장
    LinkedHashMap <Character, Integer> map = new LinkedHashMap <>();
    // 횟수가 1 인 문자 선입선출
    Queue <Character> queue = new LinkedList <> ();
    char [] arr = s.toCharArray();
    
    for (int i = 0; i < arr.length; i ++) {
        char c = arr[i];
        map.put(c, map.getOrDefault(c, 0) + 1);
    }
    
    for (char c : map.keySet()) {
        if (map.get(c) == 1) queue.add(c);
    }
    
    if (queue.size() < 1) return '_';
    
    return queue.poll();
}