Проверка на уникальность символов в строке

Задача с собеседования java #1

Проверка на уникальность символов в строке

Условие: Напишите функцию на Java, которая проверяет, содержит ли заданная строка только уникальные символы. Регистр символов учитывать (например, a и A — разные символы). Если строка содержит повторяющиеся символы, функция должна вернуть false, иначе — true.

Пример:

пример работы метода

Ограничения:

• Нельзя использовать дополнительные структуры данных (например, коллекции).
• Допустимо использовать только базовые структуры, такие как массивы.
• Решение должно быть эффективным.

Решение:

решение

Объяснение:

1. Проверяем длину строки. Если она больше 128 символов (максимальное количество уникальных символов в ASCII), значит, есть повторения.
2. Используем массив boolean размером 128, где каждый индекс соответствует символу ASCII.
3. Проходим по строке и проверяем, встречался ли символ. Если да, возвращаем false. Если нет, отмечаем его в массиве.

Подробное объяснение решения

Разберем задачу и каждую часть кода подробно.

Условие задачи

Нужно проверить, содержит ли строка только уникальные символы. Это значит:

• Каждый символ в строке должен встречаться только один раз.
• Например:Строка abcdef → уникальные символы, вернем true.
  Строка hello → символ l повторяется, вернем false.

Ограничения

1. Нельзя использовать коллекции (Set, List и т.д.).
2. Нужно решить задачу эффективно по времени и памяти.

Ключевые моменты решения

1. Почему массив boolean[128]?
   В строке мы работаем с символами, которые в Java представлены как char. Каждый символ — это число от 0 до 127 в ASCII-таблице (расширенная таблица Unicode в задаче не используется). Поэтому массив длиной 128 идеально подходит для проверки повторений.
2. Как работает массив boolean[]?

1. Индексы массива соответствуют ASCII-кодам символов.
2. Значение false в массиве означает, что символ ещё не встречался.
3. Значение true — символ уже встречался.

1. Оптимизация через длину строки.
   В ASCII всего 128 символов. Если строка длиннее 128 символов, она обязательно содержит повторения (потому что символов больше, чем уникальных вариантов).

Разбор кода

Метод isUnique

метод isUnique

• Сначала проверяем длину строки.
• Если длина больше 128, то она точно содержит повторяющиеся символы. Это быстрый способ сэкономить время.

создаем массив

• Создаем массив размером 128.
• Каждый элемент в массиве — это false по умолчанию.

реализуем цикл

• Цикл: Идем по каждому символу строки.
• char currentChar = str.charAt(i): Получаем текущий символ строки.
• charSet[currentChar]: Проверяем, встречался ли этот символ раньше:Если 1. true, значит символ уже был, возвращаем false.
  Если false, отмечаем, что символ теперь встречен.
• charSet[currentChar] = true: Помеаем символ как "встреченный".

возвращаем результат

Если прошли весь цикл без повторений, возвращаем true.

Метод main

метод main

Тестируем метод с разными строками:

• "abcdef": Все символы разные → вернется true.
• "hello": Символ l повторяется → вернется false.
• "Java": Символы разные, учитывается регистр → вернется true.

Эффективность решения

1. Временная сложность:

Цикл по строке выполняется один раз.
Каждый доступ к массиву boolean[] занимает O(1).
Итог: O(n), где n — длина строки.

1. Пространственная сложность:

Используем массив фиксированного размера
boolean[128].
Итог: O(1) по памяти.