LeetCode Offer 50. First Character that Appears Only Once

class Solution:
  def firstUniqChar(self, s: str) -> str:
    chars = {}
    for c in s:
      chars[c] = chars[c] + 1 if c in chars else 1
    for c in s:
      if chars[c] == 1:
        return c
    return ' '

from collections import deque

# abaccdeff
# {a:0} | [a]
# {a:0,b:1} | [a,b]
# {a:-1,b:1} | [b]  pop out a because it appears again
# {a:-1,b:1,c:3} | [b,c]
# {a:-1,b:1,c:-1} | [b,c]   because b is valid at front, don't bother popping out c
class Solution:
  def firstUniqChar(self, s: str) -> str:
    seen = {}
    q = deque()
    for i, c in enumerate(s):
      if c not in seen:  # if first seen, record in seen and q
        seen[c] = i
        q.append(c)
      else:  # if seen, seen[c] = -1, q.pop() until q[0] is valid (appear only once)
        seen[c] = -1
        while q and seen[q[0]] == -1:
          q.popleft()
    return q[0] if q else ' '