Description:
Given a string s, return the longest palindromic substring in s.
Examples:
Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"Solution in Python:
To solve the problem of finding the longest palindromic substring in a given string s, we can use a technique called “expand around center”. This approach takes advantage of the fact that a palindrome mirrors around its center, and thus, we can check for palindromes by expanding outwards from every possible center in the string.
Python
class Solution:
def longestPalindrome(self, s: str) -> str:
# Helper function to expand around center and find palindrome
def expand_around_center(left: int, right: int) -> str:
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
# Return the palindrome substring
return s[left + 1:right]
if len(s) == 0:
return ""
longest = ""
# Iterate over each character and consider it as a potential center
for i in range(len(s)):
# Odd length palindromes (single character center)
palindrome1 = expand_around_center(i, i)
if len(palindrome1) > len(longest):
longest = palindrome1
# Even length palindromes (two character center)
palindrome2 = expand_around_center(i, i + 1)
if len(palindrome2) > len(longest):
longest = palindrome2
return longestExplanation of the Code:
- Helper Function
expand_around_center(left, right):- This function tries to expand around a given center (or pair of centers for even-length palindromes).
- It continues expanding as long as the characters on both sides are the same, indicating a palindrome.
- It returns the palindrome found by slicing the string from the expanded indices.
- Base Case Check:
- If the input string
sis empty, return an empty string.
- If the input string
- Main Loop:
- Iterate over each character in the string, treating each character as a potential center for a palindrome.
- For each character at index
i, check for both odd-length and even-length palindromes:- Odd-length palindrome: Call
expand_around_center(i, i)which treatsias the single center. - Even-length palindrome: Call
expand_around_center(i, i + 1)which treatsiandi + 1as the center.
- Odd-length palindrome: Call
- Compare the lengths of the palindromes found with the current longest palindrome and update the longest one if a longer palindrome is found.
- Return the Longest Palindrome:
- After iterating through all possible centers, return the longest palindrome found.
Solution in Javascript:
JavaScript
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
// Helper function to expand around center and find palindrome
const expandAroundCenter = (left, right) => {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
// Return the palindrome substring
return s.slice(left + 1, right);
};
if (s.length === 0) {
return "";
}
let longest = "";
// Iterate over each character and consider it as a potential center
for (let i = 0; i < s.length; i++) {
// Odd length palindromes (single character center)
let palindrome1 = expandAroundCenter(i, i);
if (palindrome1.length > longest.length) {
longest = palindrome1;
}
// Even length palindromes (two character center)
let palindrome2 = expandAroundCenter(i, i + 1);
if (palindrome2.length > longest.length) {
longest = palindrome2;
}
}
return longest;
};
// Example usage:
console.log(longestPalindrome("babad")); // Output: "bab" or "aba"
console.log(longestPalindrome("cbbd")); // Output: "bb"Solution in Java:
Java
class Solution {
// Helper method to expand around the center and find the palindrome
private String expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
// Return the palindrome substring
return s.substring(left + 1, right);
}
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}
String longest = "";
// Iterate over each character and consider it as a potential center
for (int i = 0; i < s.length(); i++) {
// Odd length palindromes (single character center)
String palindrome1 = expandAroundCenter(s, i, i);
if (palindrome1.length() > longest.length()) {
longest = palindrome1;
}
// Even length palindromes (two character center)
String palindrome2 = expandAroundCenter(s, i, i + 1);
if (palindrome2.length() > longest.length()) {
longest = palindrome2;
}
}
return longest;
}
// Main method for testing
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.longestPalindrome("babad")); // Output: "bab" or "aba"
System.out.println(sol.longestPalindrome("cbbd")); // Output: "bb"
}
}Solution in C#:
C#
public class Solution {
// Helper method to expand around the center and find the palindrome
private string ExpandAroundCenter(string s, int left, int right) {
while (left >= 0 && right < s.Length && s[left] == s[right]) {
left--;
right++;
}
// Return the palindrome substring
return s.Substring(left + 1, right - left - 1);
}
public string LongestPalindrome(string s) {
if (string.IsNullOrEmpty(s)) {
return "";
}
string longest = "";
// Iterate over each character and consider it as a potential center
for (int i = 0; i < s.Length; i++) {
// Odd length palindromes (single character center)
string palindrome1 = ExpandAroundCenter(s, i, i);
if (palindrome1.Length > longest.Length) {
longest = palindrome1;
}
// Even length palindromes (two character center)
string palindrome2 = ExpandAroundCenter(s, i, i + 1);
if (palindrome2.Length > longest.Length) {
longest = palindrome2;
}
}
return longest;
}
}