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.

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 for Longest Palindromic Substring LeetCode Solution :

1. 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.
2. 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.
3. 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.
4. 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:
5. 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.
6. After completing the iteration, return the longest palindromic substring by extracting it from the input string s using the start and maxLength values.

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

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