387. First Unique Character in a String

리트코드 387번 풀이

문제

First Unique Character in a String

풀이

아이디어

문자열을 한 번 순회하면서 각 문자의 등장 횟수를 Map에 저장해준다. 그리고 다시 문자열을 순회하면서 등장 횟수가 1인 문자가 처음으로 나오는 인덱스를 반환한다. 만약 그런 문자가 없다면 -1을 반환한다.

코드

function firstUniqChar(s: string): number {
  const map = new Map();

  for (let c of s) {
    if (map.has(c)) map.set(c, map.get(c) + 1);
    else map.set(c, 1);
  }

  for (let idx = 0; idx < s.length; idx++) {
    if (map.get(s[idx]) === 1) return idx;
  }

  return -1;
}

시간 / 공간 복잡도

• 시간 복잡도: O(n)
• 공간 복잡도: O(1) — 알파벳 소문자만 등장하므로 Map 크기는 최대 26 (상수이므로 1)