Как определишь что все символы в строке уникальны?

Определение уникальности всех символов в строке

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

Подход 1: Наивное решение с вложенными циклами

Проверяем каждый символ против всех остальных:

def is_unique_naive(s: str) -> bool:
    """
    Проверить уникальность символов перебором
    Временная сложность: O(n²)
    Пространственная сложность: O(1)
    """
    for i in range(len(s)):
        for j in range(i + 1, len(s)):
            if s[i] == s[j]:
                return False
    return True

# Примеры
print(is_unique_naive("hello"))        # False (e,l повторяются)
print(is_unique_naive("abcdef"))       # True
print(is_unique_naive("programming")) # False (m,r повторяются)

Плюсы: простота, не требует дополнительной памяти Минусы: медленно при больших строках O(n²)

Подход 2: Использование Set (рекомендуется)

Самый практичный и часто используемый способ:

def is_unique_set(s: str) -> bool:
    """
    Проверить уникальность через множество
    Временная сложность: O(n)
    Пространственная сложность: O(min(n, alphabet_size))
    """
    return len(s) == len(set(s))

# Примеры
test_cases = [
    ("hello", False),
    ("abcdef", True),
    ("programming", False),
    ("xyz", True),
    ("", True),
    ("a", True),
]

for string, expected in test_cases:
    result = is_unique_set(string)
    status = "✓" if result == expected else "✗"
    print(f"{status} '{string}' → {result} (ожидалось {expected})")

Плюсы:

• Быстро O(n)
• Понятно читается
• Часто используется на практике

Минусы:

• Использует дополнительную память O(n)

Подход 3: Использование Dictionary/Counter

from collections import Counter

def is_unique_counter(s: str) -> bool:
    """
    Проверить уникальность через счётчик
    Временная сложность: O(n)
    Пространственная сложность: O(n)
    """
    counts = Counter(s)
    return all(count == 1 for count in counts.values())

# Более подробный вариант
def is_unique_counter_detailed(s: str) -> bool:
    """Вариант с явным подсчётом"""
    char_count = {}
    for char in s:
        if char in char_count:
            return False  # Сразу обнаружили дубликат
        char_count[char] = 1
    return True

Подход 4: Оптимальное решение с ранней остановкой

Сочетает быстроту set() и возможность остановиться раньше:

def is_unique_optimized(s: str) -> bool:
    """
    Оптимальное решение: ранняя остановка + эффективность
    """
    seen = set()
    for char in s:
        if char in seen:
            return False  # Сразу возвращаем, не нужно проверять дальше
        seen.add(char)
    return True

# Пример работы
print(is_unique_optimized("hello"))  # False (на букве 'l' уже вернёт False)

Подход 5: Для ASCII символов (ограниченный алфавит)

Если известно, что используются только ASCII символы (256 вариантов):

def is_unique_ascii(s: str) -> bool:
    """
    Оптимизация для ASCII (если длина > 256, то точно есть дубликаты)
    Временная сложность: O(n)
    Пространственная сложность: O(1) - размер фиксирован (256 или 128)
    """
    # Если символов больше чем возможно уникальных - есть дубликаты
    if len(s) > 256:
        return False
    
    # Используем массив вместо set для O(1) доступа
    char_set = [False] * 256
    
    for char in s:
        ascii_val = ord(char)
        if char_set[ascii_val]:
            return False
        char_set[ascii_val] = True
    
    return True

Подход 6: Через сортировку (не рекомендуется)

def is_unique_sorted(s: str) -> bool:
    """
    Проверка через сортировку
    Временная сложность: O(n log n)
    Пространственная сложность: O(n)
    """
    sorted_str = sorted(s)
    for i in range(len(sorted_str) - 1):
        if sorted_str[i] == sorted_str[i + 1]:
            return False
    return True

Минусы: медленнее (O(n log n) вместо O(n)), чем set подход

Сравнение всех подходов

Практический тест производительности

import time

def benchmark():
    test_string = "abcdefghijklmnopqrstuvwxyz" * 100
    methods = {
        "Set": is_unique_set,
        "Optimized": is_unique_optimized,
        "Counter": is_unique_counter,
        "ASCII": is_unique_ascii,
        "Sorted": is_unique_sorted,
    }
    
    for name, func in methods.items():
        start = time.time()
        for _ in range(10000):
            func(test_string)
        end = time.time()
        print(f"{name:15} {(end-start)*1000:.2f} ms")

# Результаты (примерные):
# Set             2.50 ms     ← ЛУЧШЕ
# Optimized       2.80 ms     ← Примерно же
# Counter         5.20 ms
# ASCII           1.80 ms     ← Лучше всех для ASCII
# Sorted         15.30 ms

Edge cases (граничные случаи)

def test_edge_cases():
    """Тестирование граничных случаев"""
    test_cases = [
        ("", True),                    # Пустая строка
        ("a", True),                   # Один символ
        ("aa", False),                 # Два одинаковых
        (" ", True),                   # Пробел
        ("  ", False),                 # Два пробела
        ("abc123", True),              # Буквы + цифры
        ("abc123abc", False),          # Повторения
        ("HELLO", False),              # Заглавные буквы (e,l повторяются)
        ("HeLLo", False),              # Смешанный регистр
    ]
    
    for string, expected in test_cases:
        result = is_unique_optimized(string)
        assert result == expected, f"Ошибка для '{string}'"
        print(f"✓ '{string}' → {result}")

test_edge_cases()

Вариант с дополнительной логикой (для интервью)

def is_unique_detailed(s: str, case_sensitive: bool = True) -> bool:
    """
    Расширенная версия с опциями
    
    Args:
        s: строка для проверки
        case_sensitive: учитывать ли регистр букв
    """
    # Нормализуем строку если нужно
    if not case_sensitive:
        s = s.lower()
    
    # Игнорируем пробелы (часто требуется на интервью)
    s = s.replace(" ", "")
    
    # Проверяем уникальность
    return len(s) == len(set(s))

# Примеры
print(is_unique_detailed("HeLLo"))                    # False
print(is_unique_detailed("HeLLo", case_sensitive=False))  # False
print(is_unique_detailed("abc def"))                 # True (пробел игнорируется)
print(is_unique_detailed("abc defabc"))              # False

Что нужно знать при ответе на интервью

1. Начните с простого решения:

• Объясните идею set()
• Покажите code: len(s) == len(set(s))

2. Обсудите trade-offs:

• Время: O(n) — отлично
• Память: O(n) — может быть проблемой для очень больших строк

3. Предложите оптимизацию:

• Ранняя остановка через перебор
• Для ASCII: использовать массив вместо set

4. Упомяните edge cases:

• Пустая строка
• Один символ
• Пробелы и спецсимволы

5. Спросите уточнения:

• Какой алфавит? (ASCII, Unicode)
• Какие размеры строк? (маленькие vs огромные)
• Нужна ли экономия памяти? (критерий: время vs память)