{{ cat }}'s docs

array 02: fist not repeating character

1. 题目

Note: Write a solution that only iterates over the string once and uses O(1) additional memory, since this is what you would be asked to do during a real interview.

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


  • For s = "abacabad", the output should be
    firstNotRepeatingCharacter(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
    firstNotRepeatingCharacter(s) = '_'.
    There are no characters in this string that do not repeat.


  • [time limit] 4000ms (py)
  • [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.

2. 解法


def firstNotRepeatingCharacter(s):
    records = {}
    for i in range(0, len(s)):
        char = s[i]
        if not char in records:
            records[char] = [i,0]
            records[char][1] += 1

    not_repeat_records = {i: j[0] for i, j in records.items() if j[1] == 0}
    if not_repeat_records:
        first_not_repeat_record = sorted(not_repeat_records.items(), key=lambda x: x[1])
        first_not_repeat_char = first_not_repeat_record[0][0]
        return first_not_repeat_char
        return "_"


def firstNotRepeatingCharacter(s):
    for c in s:
        if s.find(c) == s.rfind(c):
            return c
    return '_'