5. Longest Palindromic Substring

The Longest Palindromic Substring problem can be solved using dynamic programming. The idea is to use a 2D array to store whether a substring is a palindrome or not. We then traverse the string using two nested loops and update the array based on whether the characters at the beginning and end of the substring are equal and the substring in between them is also a palindrome. The final result is the longest palindromic substring.

C#

In C#, we can solve this problem using dynamic programming. The idea is to use a 2D array to store whether a substring is a palindrome or not. Here’s the code:

public string LongestPalindrome(string s) {
    int n = s.Length;
    bool[,] dp = new bool[n, n];
    string ans = "";
    
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            dp[i, j] = (s[i] == s[j] && (j - i < 2 || dp[i + 1, j - 1]));
            
            if (dp[i, j] && j - i + 1 > ans.Length) {
                ans = s.Substring(i, j - i + 1);
            }
        }
    }
    
    return ans;
}

C++

In C++, we can solve this problem using a similar approach as the C# solution. The idea is to use a 2D array to store whether a substring is a palindrome or not. Here’s the code:

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        bool dp[n][n];
        string ans = "";
        
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                dp[i][j] = (s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]));
                
                if (dp[i][j] && j - i + 1 > ans.length()) {
                    ans = s.substr(i, j - i + 1);
                }
            }
        }
        
        return ans;
    }
};

JavaScript

In JavaScript, we can solve this problem using a similar approach as the C# and C++ solutions. The idea is to use a 2D array to store whether a substring is a palindrome or not. Here’s the code:

var longestPalindrome = function(s) {
    let n = s.length;
    let dp = [];
    let ans = "";
    
    for (let i = n - 1; i >= 0; i--) {
        dp[i] = [];
        for (let j = i; j < n; j++) {
            dp[i][j] = (s[i] === s[j] && (j - i < 2 || dp[i + 1][j - 1]));
            
            if (dp[i][j] && j - i + 1 > ans.length) {
                ans = s.substring(i, j - i + 1);
            }
        }
    }
    
    return ans;
};

Python

In Python, we can solve this problem using a similar approach as the C#, C++, and JavaScript solutions. The idea is to use a 2D array to store whether a substring is a palindrome or not. Here’s the code:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False for j in range(n)] for i in range(n)]
        ans = ""
        
        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                dp[i][j] = (s[i] == s[j] and (j - i < 2 or dp[i + 1][j - 1]))
                
                if dp[i][j] and j - i + 1 > len(ans):
                    ans = s[i:j + 1]
        
        return ans

Conclusion

In this article, we looked at how to solve the Longest Palindromic Substring problem in four different programming languages (C#, C++, JavaScript, and Python). The approach was to use dynamic programming and a 2D array to store whether a substring is a palindrome or not. The code for each language is similar in structure and the main difference is in syntax.

I hope this article has been helpful in showing you how to solve the Longest Palindromic Substring problem in multiple languages. Good luck with your coding!

Time and space complexity

The time complexity of the above solutions is O(n^2), where n is the length of the input string. This is because we are using nested loops to traverse the entire string and check whether each substring is a palindrome or not.

The space complexity of the solutions is O(n^2), where n is the length of the input string. This is because we are using a 2D array to store the results of whether each substring is a palindrome or not.

It is important to note that these solutions are not the most efficient and there are more optimized solutions available with better time and space complexity. However, these solutions provide a good starting point for understanding the problem and the approach to solve it.

0

0