Longest Palindrome Inside a String
You get a string s of lowercase English letters.
A palindrome reads the same from left to right and from right to left, for example "level" or "abba". A substring is a part of s with no gaps.
Return the longest substring of s that is a palindrome.
Tie rule
If several palindromic substrings have the largest length, return the one that starts at the smallest index.
Note
Every single letter is a palindrome, so the answer always has at least one letter.
Hint
Every palindrome has a centre. The centre is one letter (odd length) or the gap between two letters (even length). For each of the 2n - 1 centres, grow outwards while the letters on both sides are equal. This is O(n²) time and O(1) extra space.
Examples
Example 1
- Input:
- "xracecarz"
- Output:
- "racecar"
"racecar" (index 1 to 7) reads the same in both directions. No longer palindrome exists in the string.
Example 2
- Input:
- "abbcdde"
- Output:
- "bb"
"bb" and "dd" both have length 2, and there is no palindrome of length 3 or more. "bb" starts first (index 1), so it is the answer.
Example 3
- Input:
- "qwerty"
- Output:
- "q"
No two letters are equal, so every palindrome has length 1. The first one is "q".
Constraints
1 <= s.length <= 60scontains only lowercase English letters.
Run checks your code against the 3 examples. Submit checks it against all 223 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.