Как находить кратчайшее расстояние между повторяющимися символами?

Поиск кратчайшего расстояния между повторяющимися символами

Задача заключается в том, чтобы найти минимальное расстояние между двумя одинаковыми символами в строке. Расстояние обычно измеряется как разность индексов (абсолютное значение). Это классическая задача на обработку строк, которая проверяет умение эффективно использовать хеш-таблицы или массивы для отслеживания позиций символов.

Алгоритм

Мы можем решить задачу за один проход по строке, используя словарь для хранения последнего вхождения каждого символа. При встрече символа, который уже встречался, вычисляем расстояние до его предыдущей позиции и обновляем минимальное значение. Если символ встречается впервые, просто сохраняем его индекс.

Пример кода на JavaScript

function minDistanceBetweenRepeats(str) {
  const lastPos = {};
  let minDist = Infinity;
  for (let i = 0; i < str.length; i++) {
    const char = str[i];
    if (char in lastPos) {
      const dist = i - lastPos[char];
      if (dist < minDist) minDist = dist;
    }
    lastPos[char] = i;
  }
  return minDist === Infinity ? -1 : minDist;
}

console.log(minDistanceBetweenRepeats("abca")); // 3 (a на 0 и 3)
console.log(minDistanceBetweenRepeats("abcabc")); // 3 (a на 0 и 3)

Применение

Подобные алгоритмы используются в задачах сжатия данных, поиска паттернов и анализа текста. Например, для определения повторяющихся подстрок или оценки разнообразия символов.

Вывод: Данный подход эффективен благодаря однопроходному алгоритму с использованием хеш-таблицы, что даёт временную сложность O(n) и память O(k), где k — количество уникальных символов. Применяйте его, когда нужно быстро найти минимальное расстояние между одинаковыми элементами в последовательности.