Уникальные символы в строке

Решение

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

Решение 1: Без дополнительных структур — Сортировка

Если буквально не использовать дополнительные структуры, можно отсортировать символы и проверить соседние элементы. Это использует встроенные функции, но не создаёт новые структуры данных явно.

def has_unique_chars_sorted(s: str) -> bool:
    """
    Определяет уникальность символов без явного использования структур данных.
    Использует встроенную сортировку.
    
    Args:
        s: Входная строка
    
    Returns:
        True если все символы уникальны, False иначе
    
    Time Complexity: O(n log n)
    Space Complexity: O(1) если не считать встроенную сортировку
    """
    # Преобразуем в список и сортируем
    chars = sorted(s)
    
    # Проверяем соседние элементы
    for i in range(len(chars) - 1):
        if chars[i] == chars[i + 1]:
            return False
    
    return True

Решение 2: Двойной цикл (Самое буквальное)

Самый базовый подход — сравнить каждый символ с остальными. Не использует вообще никаких структур данных.

def has_unique_chars_brute_force(s: str) -> bool:
    """
    Проверка уникальности символов двойным циклом.
    Не использует никаких структур данных кроме переменных.
    
    Args:
        s: Входная строка
    
    Returns:
        True если все символы уникальны, False иначе
    
    Time Complexity: O(n²)
    Space Complexity: 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

Решение 3: Битовая маска (Оптимально для ASCII)

Если известно, что строка содержит только ASCII символы (до 128), используем битовую маску вместо HashSet.

def has_unique_chars_bitwise(s: str) -> bool:
    """
    Использует битовую маску для отслеживания символов.
    Оптимально для ASCII символов.
    
    Args:
        s: Входная строка
    
    Returns:
        True если все символы уникальны, False иначе
    
    Time Complexity: O(n)
    Space Complexity: O(1) — используем один integer
    """
    # Битовая маска для 128 ASCII символов
    char_set = 0
    
    for char in s:
        # Получаем позицию бита для текущего символа
        char_value = ord(char)
        
        # Проверяем, был ли этот символ встречен ранее
        if (char_set & (1 << char_value)) > 0:
            return False
        
        # Помечаем символ как встреченный
        char_set |= (1 << char_value)
    
    return True

Решение 4: Ограничение на набор символов

Если строка содержит только латинские буквы нижнего регистра (a-z):

def has_unique_chars_limited_ascii(s: str) -> bool:
    """
    Проверка для строк с ограниченным набором символов (a-z).
    Использует битовую маску для 26 букв.
    
    Args:
        s: Входная строка с только a-z символами
    
    Returns:
        True если все символы уникальны, False иначе
    
    Time Complexity: O(n)
    Space Complexity: O(1) — один integer вместо 26 булевых значений
    """
    if len(s) > 26:  # Больше 26 символов — гарантированно есть дубликат
        return False
    
    char_mask = 0
    
    for char in s:
        # Для букв a-z: смещение от 0 до 25
        bit_position = ord(char) - ord(a)
        
        if (char_mask & (1 << bit_position)) > 0:
            return False
        
        char_mask |= (1 << bit_position)
    
    return True

Примеры использования

# Тестовые случаи
test_cases = [
    ("abcdef", True),
    ("hello", False),
    ("", True),
    ("a", True),
    ("aa", False),
    ("abcdefghijklmnopqrstuvwxyz", True),
    ("The quick brown fox jumps over the lazy dog", False),
]

# Все функции дают одинаковый результат
for s, expected in test_cases:
    assert has_unique_chars_sorted(s) == expected
    assert has_unique_chars_brute_force(s) == expected
    assert has_unique_chars_bitwise(s) == expected
    
print("Все тесты пройдены!")

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

Интерпретация задачи

Важно уточнить, что означает "без дополнительных структур данных":

• Строго: Только переменные, циклы и базовые операции (двойной цикл)
• Разумно: Встроенные функции (сортировка) без явного HashSet
• Оптимально: Битовая маска как компактное представление вместо массива/HashSet

Для собеседования QA Automation Engineer часто ожидают решение с HashSet (O(n)), но с понимаем причин ограничений и альтернативных подходов.