Solution For Longest Palindrome

The problem is to find the longest palindrome substring in a given string.

Solution:

One way to solve this problem is to use a dynamic programming approach. We can create a 2D boolean array dp[l][r], where dp[l][r] is true if the substring from index l to index r in the string s is a palindrome. The base cases are when l=r and l=r+1.

The recurrence relation is:

• dp[l][r] = true if dp[l+1][r-1] is true and s[l] = s[r]
• dp[l][r] = false if s[l] != s[r]

We can initialize the dp array with all false values and then fill it in from the bottom up and left to right.

Algorithm:

1. Initialize a 2D boolean array dp with size n*n where n is the length of the input string s.
2. Initialize all diagonal elements dp[i][i] and dp[i][i+1] (i.e., substrings of length 1 and 2) as true.
3. Traverse the input string s starting from length 3 and iterate over all possible substrings of length i from j, where dp[j][j+i-1] is true if s[j] = s[j+i-1] and dp[j+1][j+i-2] is true.
4. Update longest_palindrome if the length of the current substring (i.e., j+i-1-j+1) is greater than the current longest_palindrome.
5. Return longest_palindrome.

Time Complexity: O(n^2)

Let’s implement the above algorithm:

Python Code:

class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
dp = [[False for j in range(n)] for i in range(n)]

    longest_palindrome = ""
    for i in range(n):
        dp[i][i] = True
        longest_palindrome = s[i]

    for i in range(n-1):
        if s[i] == s[i+1]:
            dp[i][i+1] = True
            longest_palindrome = s[i:i+2]

    for i in range(3, n+1):
        for j in range(n-i+1):
            k = j + i - 1
            if s[j] == s[k] and dp[j+1][k-1]:
                dp[j][k] = True
                if i > len(longest_palindrome):
                    longest_palindrome = s[j:k+1]

    return longest_palindrome

Input:

s = “babad”

Output:

“bab”

Explanation:

The longest palindromic substring in “babad” is “bab”.

Step by Step Implementation For Longest Palindrome

public class Solution {
    public int longestPalindrome(String s) {
        if (s == null || s.length() == 0) return 0;
        HashSet set = new HashSet();
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (set.contains(c)) {
                set.remove(c);
                count++;
            } else {
                set.add(c);
            }
        }
        if (!set.isEmpty()) return count * 2 + 1;
        return count * 2;
    }
}

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # Base cases
        if len(s) == 0:
            return ""
        if len(s) == 1:
            return s
        
        # Initialize max_length and max_substring
        max_length = 1
        max_substring = s[0]
        
        # Iterate through the string
        for i in range(len(s)):
            
            # For odd length palindromes
            curr_length = self.find_palindrome_length(s, i, i)
            if curr_length > max_length:
                max_length = curr_length
                max_substring = s[i-max_length+1:i+1]
                
            # For even length palindromes
            curr_length = self.find_palindrome_length(s, i, i+1)
            if curr_length > max_length:
                max_length = curr_length
                max_substring = s[i-max_length+1:i+2]
                
        return max_substring
    
    # Helper function to find the length of a palindrome centered at i, j
    def find_palindrome_length(self, s, i, j):
        while i >= 0 and j < len(s) and s[i] == s[j]:
            i -= 1
            j += 1
        return j-i-1

var longestPalindrome = function(s) {
    let longest = "";
    
    for (let i = 0; i < s.length; i++) {
        for (let j = i + 1; j <= s.length; j++) {
            const current = s.slice(i, j);
            if (isPalindrome(current) && current.length > longest.length) {
                longest = current;
            }
        }
    }
    
    return longest;
};

function isPalindrome(s) {
    let left = 0;
    let right = s.length - 1;
    
    while (left < right) {
        if (s[left] !== s[right]) {
            return false;
        }
        
        left++;
        right--;
    }
    
    return true;
}

class Solution {
public:
    int longestPalindrome(string s) {
        // Corner cases
        if (s.length() == 0) return 0;
        if (s.length() == 1) return 1;
        
        // Initialize variables
        int n = s.length();
        int max_len = 1;
        bool table[n][n];
        memset(table, 0, sizeof(table));
        
        // Fill the table for substrings of length 2
        for (int i = 0; i < n-1; i++) {
            if (s[i] == s[i+1]) {
                table[i][i+1] = true;
                max_len = 2;
            }
        }
        
        // Fill the table for substrings of length 3 and above
        for (int k = 3; k <= n; k++) {
            for (int i = 0; i < n-k+1; i++) {
                int j = i+k-1;
                if (table[i+1][j-1] && s[i] == s[j]) {
                    table[i][j] = true;
                    if (k > max_len) max_len = k;
                }
            }
        }
        
        return max_len;
    }
};

public class Solution {
    public int LongestPalindrome(string s) {
        if (string.IsNullOrEmpty(s))
        {
            return 0;
        }
        int maxLength = 1;
        int start = 0;
        int low, high;
 
        // One by one consider every character as center point of 
        // even and length palindromes
        for (int i = 1; i < s.Length; ++i)
        {
            // Find the longest even length palindrome with center
            // points as i-1 and i.  
            low = i - 1;
            high = i;
            while (low >= 0 && high < s.Length && s[low] == s[high])
            {
                if (high - low + 1 > maxLength)
                {
                    start = low;
                    maxLength = high - low + 1;
                }
                --low;
                ++high;
            }
 
            // Find the longest odd length palindrome with center 
            // point as i
            low = i - 1;
            high = i + 1;
            while (low >= 0 && high < s.Length && s[low] == s[high])
            {
                if (high - low + 1 > maxLength)
                {
                    start = low;
                    maxLength = high - low + 1;
                }
                --low;
                ++high;
            }
        }
 
        return maxLength;
    }
}