Первый неповторяющийся символ

Решение: Первый неповторяющийся символ

Эта задача требует поиска первого символа, который встречается только один раз в строке. Решается за два прохода по строке: первый для подсчёта частоты символов, второй для поиска первого неповторяющегося.

Алгоритм решения

1. Создаём словарь/хеш-таблицу для подсчёта частоты каждого символа
2. Первый проход: Проходим по строке и считаем, сколько раз встречается каждый символ
3. Второй проход: Проходим по строке заново и возвращаем первый символ с частотой 1
4. Если таких нет: Возвращаем -1 или None (в зависимости от требований)

Реализация решения

def firstUniqChar(s: str) -> int:
    """
    Находит индекс первого неповторяющегося символа.
    
    Args:
        s: Входная строка
    
    Returns:
        Индекс первого неповторяющегося символа или -1 если такого нет
    """
    # Подсчитываем частоту каждого символа
    char_count = {}
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1
    
    # Ищем первый символ с частотой 1
    for i, char in enumerate(s):
        if char_count[char] == 1:
            return i
    
    # Если неповторяющегося символа нет
    return -1

# Альтернативный вариант, возвращающий сам символ
def firstUniqCharSymbol(s: str) -> str:
    """
    Находит первый неповторяющийся символ в строке.
    
    Returns:
        Первый неповторяющийся символ или пустая строка
    """
    char_count = {}
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1
    
    for char in s:
        if char_count[char] == 1:
            return char
    
    return ""

Пошаговый разбор примеров

Пример 1: "leetcode"

Первый проход (подсчёт частоты):

char_count = {
    l: 1,
    e: 3,
    t: 1,
    c: 1,
    o: 1,
    d: 1
}

Второй проход (поиск первого неповторяющегося):

• Индекс 0: l, char_count[l] = 1 → Возвращаем 0 (или символ l)

Выход: 0 (или l) ✓

Пример 2: "loveleetcode"

Первый проход (подсчёт частоты):

char_count = {
    l: 2,
    o: 2,
    v: 1,
    e: 4,
    t: 1,
    c: 1,
    d: 1
}

Второй проход (поиск первого неповторяющегося):

• Индекс 0: l, char_count[l] = 2 → пропускаем
• Индекс 1: o, char_count[o] = 2 → пропускаем
• Индекс 2: v, char_count[v] = 1 → Возвращаем 2 (или символ v)

Выход: 2 (или v) ✓

Реализация с использованием Counter

from collections import Counter

def firstUniqChar_with_counter(s: str) -> int:
    """
    Использует Counter из модуля collections для упрощения кода
    """
    char_count = Counter(s)
    
    for i, char in enumerate(s):
        if char_count[char] == 1:
            return i
    
    return -1

Реализация с сохранением порядка вставки (OrderedDict)

from collections import OrderedDict

def firstUniqChar_ordered(s: str) -> int:
    """
    Использует OrderedDict для явного сохранения порядка
    (хотя с Python 3.7+ обычный dict тоже сохраняет порядок)
    """
    char_count = OrderedDict()
    
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1
    
    for i, char in enumerate(s):
        if char_count[char] == 1:
            return i
    
    return -1

Тестовые случаи

# Основные примеры
print(firstUniqChar("leetcode"))           # 0
print(firstUniqCharSymbol("leetcode"))     # "l"

print(firstUniqChar("loveleetcode"))       # 2
print(firstUniqCharSymbol("loveleetcode")) # "v"

# Граничные случаи
print(firstUniqChar(""))              # -1
print(firstUniqChar("a"))             # 0
print(firstUniqChar("aa"))            # -1
print(firstUniqChar("aabbcc"))        # -1
print(firstUniqChar("abcdefg"))       # 0
print(firstUniqChar("aabccd"))        # 3

# Специальные случаи
print(firstUniqChar("  a  b  "))      # 2 (пробелы тоже символы)
print(firstUniqChar(".,.,.,a"))       # 6

Сложность

• Временная сложность: O(n), два линейных прохода по строке
• Пространственная сложность: O(1), в худшем случае O(k), где k — размер алфавита (максимум 26 для букв, 128-256 для ASCII, 1114112 для Unicode, но практически ограничено входными данными)

Оптимизация для больших строк

def firstUniqChar_optimized(s: str) -> int:
    """
    Если строка содержит много одинаковых символов,
    можем выйти рано из второго прохода
    """
    if not s:
        return -1
    
    char_count = {}
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1
    
    # Второй проход с ранним выходом
    for i in range(len(s)):
        if char_count[s[i]] == 1:
            return i
    
    return -1

Важные детали

• Регистр символов имеет значение (A ≠ a)
• Пробелы и специальные символы считаются обычными символами
• Пустая строка возвращает -1
• Строка из одного символа всегда возвращает индекс 0

Решение оптимально, имеет линейную сложность и подходит для production-кода.