Longest Palindromic Substring LeetCode Solution
Longest Palindromic Substring :
Given a string s, return the longest palindromic substring in s. Palindromic Substring :- A palindromic substring is a sequence of characters within a string that reads the same forwards as it does backward.
- In other words, if you reverse the characters of a palindromic substring, it will still be the same as the original sequence.
- Palindromic substrings are symmetric, and they can consist of letters, digits, or other characters.
Example 1 :
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Longest Palindromic Substring LeetCode Solution :
Constraints :
- 1 <= s.length <= 1000
- s consist of only digits and English letters.
Example 2 :
- Input: s = “cbbd”
- Output: “bb”
Approach
The approach for solving the "Longest Palindromic Substring" problem on LeetCode involves dynamic programming. In this approach, we initialize a 2D boolean array to track whether substrings are palindromes or not. We then iterate through the input string, comparing characters and updating the array based on palindrome conditions. Specifically, if characters at both ends of a substring match and the inner substring is also a palindrome, we mark the entire substring as a palindrome.
Approach for Longest Palindromic Substring LeetCode Solution :
- Initialize a 2D boolean array dp of size n x n, where n is the length of the input string s. dp[i][j] will be True if the substring from index i to j is a palindrome, and False otherwise. Initialize all elements of dp to False.
- Initialize two variables, start and maxLength, to keep track of the starting index and length of the longest palindromic substring found so far. Initially, set start = 0 and maxLength = 1 because each individual character is a palindrome of length 1.
- Iterate over the string s with two nested loops. The outer loop iterates from the end of the string towards the beginning, and the inner loop iterates from the current position to the end of the string.
- For each pair of indices i and j, check if s[i] == s[j] and if the substring between i and j is a palindrome. To determine this, use the following conditions:
- If s[i] == s[j] and j – i <= 2, set dp[i][j] = True. This covers the cases of single characters and adjacent characters.
If s[i] == s[j] and dp[i + 1][j – 1] is True, then set dp[i][j] = True. This means that the substring from i to j is a palindrome if the substring from i + 1 to j – 1 is also a palindrome.
During the iteration, if you encounter a longer palindrome (i.e., j – i + 1 is greater than maxLength), update start to i and maxLength to j – i + 1. - After completing the iteration, return the longest palindromic substring by extracting it from the input string s using the start and maxLength values.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code for Longest Palindromic Substring LeetCode Solution :
C++
Java
Python
C++
class Solution {
private:
bool check(string &s, int i, int j){
while(i< j){
if(s[i] != s[j]){
return false;
}
i++;
j--;
}
return true;
}
public:
string longestPalindrome(string s) {
int n = s.size();
int starting_index = 0;
int max_len = 0;
for(int i=0; i< n; i++){
for(int j=i; j< n; j++){ if(check(s, i, j)){ if(j-i+1 > max_len){
max_len = j-i+1;
starting_index = i;
}
}
}
}
return s.substr(starting_index, max_len);
}
};
Java
class Solution {
public String longestPalindrome(String s) {
int max=0;
String answer="";
for(int i=0;i<s.length();i++){
if(i!=0 && s.charAt(i)==s.charAt(i-1)){
int cur = fun(i-2,i+1,s)+2;
if(max<cur){
max = cur;
answer = s.substring(i-cur/2,i+cur/2);
}
}
int cur = fun(i-1,i+1,s)+1;
if(max<cur){
max = cur;
answer = s.substring(i-cur/2,i+1+cur/2);
}
}
return answer;
}
private int fun(int l, int r, String s){
if(l<0 || r>=s.length() || s.charAt(l)!=s.charAt(r)) return 0;
return 2+fun(l-1,r+1,s);
}
}
Python
class Solution:
def longestPalindrome(self, s: str) -> str:
if s == s[::-1]: return s
start, size = 0, 1
for i in range(1, len(s)):
l, r = i - size, i + 1
s1, s2 = s[l-1:r], s[l:r]
if l - 1 >= 0 and s1 == s1[::-1]:
start, size = l - 1, size + 2
elif s2 == s2[::-1]:
start, size = l, size + 1
return s[start:start+size]
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment