LeetCode #5 Longest Palindromic Substring Solution & Explanation

LeetCode Problem

Given a string s, return the longest palindromic substring in s.

(A string is palindromic if it reads the same forward and backward.)

💡Hint 1

How can we reuse a previously computed palindrome to compute a larger palindrome?

💡Hint 2

If “aba” is a palindrome, is “xabax” a palindrome? Similarly is “xabay” a palindrome?

💡Hint 3

Complexity based hint:
If we use brute-force and check whether for every start and end position a substring is a palindrome we have O(n^2) start – end pairs and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(1) by reusing some previous computation.

Solution

In this problem, we can apply dynamic programming to divide the problem.

C# Solution

Solution1

public class Solution {
    public string LongestPalindrome(string s) {
        int n = s.Length;
        bool[] dp = new bool[n];
        
        //Initialize the answer. Since s.Length >= 1, the first character itself is a palindrome substring.
        int start = 0;
        int maxLength = 1;

        //i indicates the start of the substring, while j indicates the end of the substring.
        for (int i = n-1; i >= 0; i--)
        {
            for (int j = n-1; j >= i; j--) 
            {
                dp[j] = s[i] == s[j] && (j - i < 3 || dp[j - 1]); 
                if (dp[j] && j - i + 1 > maxLength) 
                {
                    maxLength = j - i + 1;
                    start = i;
                }
            }
        }

        return s.Substring(start, maxLength);
    }
}

dp[j] = s[i] == s[j] && (j – i < 3 || dp[j – 1]); : there means two condition

1. j – i < 3, means length equals to 1,2,3 and that means the substring is a palindrome
   • When the length is 2, both characters must be the same to form a palindrome.
   • When the length is 3, the substring is a palindrome regardless of the character in the middle, because it’s the same as its mirror image.
   • When the length is 1, it’s always a palindrome (a single character).
     
2. dp[j – 1] == true
   • This condition checks whether the substring from index i+1 to j-1 is a palindrome. If it’s a palindrome, and the characters at indexes i and j are the same, then the entire substring from index i to j is a palindrome.

Conclusion

I’ve encountered palindrome problems before, and they didn’t seem as challenging.

However, this one appears to be more difficult…

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts, thanks a lot

✅If you got any problem about the explanation, please feel free to let me know

The problem link: Longest Palindromic Substring – LeetCode

Similar Questions

• LeetCode #9 Palindrome Number Solution & Explanation
• LeetCode #125 Valid Palindrome Solution & Explanation
• LeetCode #2108 Find First Palindromic String in the Array Solution & Explanation

Some Random LeetCode posts