Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Constraints:
- 1 <= s.length <= 1000
- s consist of only digits and English letters (lower-case and/or upper-case)
Examples:
Input: "babad"
Output: "bab"
Explanation: "bab" is a palindromic substring and the longest one.
Input: "cbbd"
Output: "bb"
Explanation: "bb" is a palindromic substring and the longest one.
Solutions
Expand Around Center
Time: O(n^2)Space: O(1)
The idea is to expand around the center of the palindrome. We consider two types of palindromes: odd length and even length. For odd length, the center is a single character. For even length, the center is between two characters.
public String longestPalindrome(String s) {
String longest = "";
for (int i = 0;
i < s.length();
i++) {
String palindrome1 = expandAroundCenter(s, i, i);
String palindrome2 = expandAroundCenter(s, i, i + 1);
longest = longest.length() > palindrome1.length() ? longest : palindrome1;
longest = longest.length() > palindrome2.length() ? longest : palindrome2;
}
return longest;
}
public String expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return s.substring(left + 1, right);
}Follow-up:
What if the input string is very large and we need to find all palindromic substrings?
