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

Вопрос:

Как найти палиндромную подстроку (расширить вокруг центра)

Начиная с центра подстроки, чтобы оценить, является ли подстрока палиндромом. Если буква слева от центра s[center-1] равна букве справа от центра s[center+1], мы продолжаем двигаться к следующей букве с каждой стороны, пока не наткнемся на неравенство:

s[center - 1] === s[center + 1]
s[center - 2] === s[center + 2]
... === ...
s[center - n] === s[center + n]
s[center - n -1] !== s[center + n + 1]//exit

Затем мы находимs.substring(center — n, center + n + 1) — палиндромную подстроку (конечный индекс javascript substring() не включает, поэтому нам нужно добавить его, чтобы захватить всю подстроку).

Существует два сценария использования центра(ов) в строке:

  • в палиндроме есть только один центр s[i], когда его длина нечетна: центр «babad» — это «b» с индексом 2
  • есть два центра s[i] и s[i+1] в палиндроме, когда его длина четна: центрами «cbbd» являются «b» с индексом 1 и «b» с индексом 2

Мы не знаем, какие строки мы получаем, поэтому нам нужно включить оба сценария.

Код и объяснение

Я установил функцию с именем findLPS(s, center1, center2), которая принимает строку, которую мы оцениваем, и оба центра. В функции есть две переменные left и right для отслеживания начального и конечного индексов подстроки. Пока left и right находятся в границах, а s[left]===s[right] продолжаем движение left влево и right вправо. Когда условие не было выполнено, мы выходим из цикла while и возвращаем длину подстроки right-left-1.

Почему длина подстроки right-left-1, а не right-left+1?

For example, when s is “aba”, left and right start at index 1, then
left--, left = 1, 0, -1
right++, right = 1, 2, 3
When we break out of the while loop, left is -1 and right is 3. We need to move back an index on both sides:
substring.length = (right-1)-(left+1)+1= (3–1)-(-1+1)+1 = 3
which equals to right-left-1 = 3-(-1)-1 = 3

В функции longestPalindrome я использовал цикл for для оценки каждой буквы в строке, чтобы увидеть, является ли она центром палиндрома, как упоминалось ранее, нам нужно включить оба сценария центра (центров). Если len длиннее longest, мы можем присвоить len longest и начать вычислять индексы start и end самой длинной палиндромной подстроки, которую мы хотим вернуть.

Почему начало i - Math.floor((len -1)/2), а не i — Math.floor(len/2)?

For example, i is at the center of the palindrome and we want to calculate the start index of the string:
"aba", i = 1, len = 3
i - Math.floor(len/2) = 1 - 1 = 0
i - Math.floor((len-1)/2) = 1 - 1 = 0
"cbbc", i =1, len = 4
i - Math.floor(len/2) = 1-2 = -1 //index out of bounds
i - Math.floor((len-1)/2) = 1 - 1 = 0 //index in the bounds
We are dealing with indexes here, when the length of the returned substring is even and the centers are i and i+1. We are using i to calculate the start and end indexes. Use "cbbc" again:
c b b c
0 1 2 3
i = 1
len = 4
len/2 = 2
Math.floor((len-1)/2) = 1
We can see that i is "closer" to the start index than to the end index. So for end index we do not need to minus one off the len:
 
end = 1 + Math.floor(4/2) = 3
start = i - Math.floor((len-1)/2) = 0

Анализ сложности

Временная сложность: O(n²). Поскольку расширение палиндрома вокруг его центра может занять O (n) времени, общая сложность составляет O (n²).

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

Ресурс: