Вчера был 63-й день моего кодинга. Я решил один вопрос.

Задача: Самый длинный палиндром в строке

Для заданной строки S найдите самую длинную палиндромную подстроку в S.Подстрока строки S: S[ i . . . . j ] где 0 ≤ i ≤ j ‹ len(S). Строка-палиндром: строка, которая читается так же в обратном порядке. Более формально, S является палиндромом, если reverse(S) = S.В случае конфликта вернуть подстроку, которая встречается первой (с наименьшим начальным индексом).

Пример 1:

Input:
S = "aaaabbaa"
Output: aabbaa
Explanation: The longest Palindromic
substring is "aabbaa".

Пример 2:

Input: 
S = "abc"
Output: a
Explanation: "a", "b" and "c" are the 
longest palindromes with same length.
The result is the one with the least
starting index.

Ваша задача
Вам не нужно ничего читать или печатать. Ваша задача — завершить функцию longestPalin(), которая принимает строку S в качестве входных данных и возвращает самую длинную палиндромную подстроку S.

Ожидаемая временная сложность:O(|S|2).
Ожидаемое вспомогательное пространство:O(1).

Решение (в Java)

  • Пройдите по строке и считайте каждый индекс средней точкой строки-палиндрома. Здесь будут встречаться два различных случая.
  • Случай 1: палиндромная строка имеет четную длину
  • В этом случае назначьте два указателя left = i — 1 и right = i в качестве центра и разверните влево и вправо в обоих направлениях, пока s[left] == ​​s[right]. Продолжайте обновлять начальный индекс и максимальную длину палиндромной строки.
  • Случай 2: палиндромная строка имеет нечетную длину
  • В этом случае два указателя будут назначены как левый = i -1 и правый = i + 1, поскольку индекс i является средним элементом. Теперь повторите тот же процесс, что и для строки четной длины.
  • Возвращает палиндромную подстроку максимальной длины.
class Solution{
    static String longestPalin(String S){
        int start=0, end=1;
        for(int i=1; i<S.length(); i++){
            int left=i-1;
            int right=i;
            while(left>=0 && right<S.length() && S.charAt(left)==S.charAt(right)){
                if(right-left+1>end){
                    start=left;
                    end= right- left+1;
                
                }
                left--;
                right++;
            }
  
        left=i-1;
        right=i+1;
           while(left>=0 && right<S.length() && S.charAt(left)==S.charAt(right)){
                if(right-left+1>end){
                    start=left;
                    end= right- left+1;
                
                }
                left--;
                right++;
            }
        }
        String ans="";
        for( int i=start; i<start+end; i++){
            ans+=S.charAt(i);
        }
        return ans;
    }
}