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

Что проверяют

Умеете ли вы отличить красивое решение в одну строку от эффективного и знаете ли, как устроены строки в JavaScript. Следом почти всегда просят игнорировать регистр и знаки препинания, а потом спрашивают про эмодзи.

Как отвечать

Начните с того, почему наивный вариант неоптимален: str.split('').reverse().join('') === str делает несколько проходов и создаёт массив и новую строку, то есть O(n) дополнительной памяти.

Оптимальный вариант это два указателя. Левый идёт с начала, правый с конца, символы сравниваются до встречи в центре, при первом несовпадении сразу возвращаем false. Время O(n), сравнений не больше n/2, память O(1).

function isPalindrome(s) {
  let l = 0, r = s.length-1;
  const ok = (c) => /[\p{L}\p{N}]/u.test(c);
  while (l < r) {
    if (!ok(s[l])) { l++; continue; }
    if (!ok(s[r])) { r--; continue; }
    if (s[l].toLowerCase() !== s[r].toLowerCase()) return false;
    l++; r--;
  }
  return true;
}

Что проговорить отдельно:

• нормализация на ходу: toLowerCase() и replace() над всей строкой заранее дают ещё один проход и копию. Пропуск лишних символов указателями сохраняет один проход;
• кириллица: регулярка [a-z] выкинет русские буквы, поэтому класс \p{L} с флагом u;
• Юникод: строки в JS хранятся в UTF-16, эмодзи занимает два кодовых блока, и сравнение по индексу разбивает суррогатную пару. Корректно работают Array.from(s) или Intl.Segmenter для графем, но это уже O(n) памяти;
• составные символы: «й» может быть записана одной или двумя кодовыми точками, поэтому перед проверкой пригодится s.normalize('NFC').

Где спотыкаются

Называют reverse() решением за один проход. Это несколько проходов и две копии данных.

Сначала чистят строку регуляркой, а потом заявляют O(1) памяти. Копия уже создана, честнее это признать.

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