Longest Palindromic Substring

1. Clarify the problem:

   • The problem requires us to find the longest palindromic substring within a given string.
   • A palindrome is a string that reads the same forward and backward.
   • We need to return the longest palindromic substring.
   • If there are multiple longest palindromic substrings, we can return any one of them.

2. Analyze the problem:

   • Input: A string of characters.
   • Output: The longest palindromic substring within the given string.
   • Constraints:
     • The given string may have uppercase and lowercase letters, digits, or special characters.
     • The length of the string can be up to 1000 characters.

3. Design an algorithm:

   • We can solve this problem using dynamic programming.
   • Create a 2D boolean table to store whether a substring is a palindrome or not.
   • Initialize all single characters as palindromes (diagonal of the table).
   • Traverse the table diagonally from the bottom-left to the top-right.
   • For each substring (i, j), check if the characters at indices i and j are equal.
   • If they are equal, check if the substring (i+1, j-1) is also a palindrome.
   • Update the table accordingly.
   • Keep track of the longest palindromic substring found and its length.
   • Return the longest palindromic substring.

4. Explain your approach:

   • We will define a function longestPalindrome that takes a string as input.
   • Create a 2D boolean table dp of size n x n, where n is the length of the input string.
   • Initialize all single characters as palindromes by setting dp[i][i] to True for all i.
   • Initialize variables max_length and start to keep track of the longest palindromic substring found and its starting index.
   • Traverse the table dp diagonally from the bottom-left to the top-right.
   • For each substring (i, j), check if the characters at indices i and j are equal.
   • If they are equal and the substring (i+1, j-1) is also a palindrome, update dp[i][j] to True.
   • Update max_length and start if the current palindrome is longer than the previous longest palindrome.
   • Finally, return the substring from start to start + max_length.

5. Write clean and readable code:

python

def longestPalindrome(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]

    max_length = 0
    start = 0

    # Initialize single characters as palindromes
    for i in range(n):
        dp[i][i] = True
        max_length = 1

    # Traverse the table diagonally
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1

            if s[i] == s[j]:
                if length == 2 or dp[i + 1][j - 1]:
                    dp[i][j] = True
                    max_length = length
                    start = i

    return s[start: start + max_length]

6. Test your code:

python

# Test case 1:
s1 = "babad"
result1 = longestPalindrome(s1)
# Expected output: "bab" or "aba"

# Test case 2:
s2 = "cbbd"
result2 = longestPalindrome(s2)
# Expected output: "bb"

# Test case 3:
s3 = "a"
result3 = longestPalindrome(s3)
# Expected output: "a"

# Test case 4:
s4 = "ac"
result4 = longestPalindrome(s4)
# Expected output: "a" or "c"

# Test case 5:
s5 = "racecar"
result5 = longestPalindrome(s5)
# Expected output: "racecar"

# Print the results
print(result1)
print(result2)
print(result3)
print(result4)
print(result5)

7. Optimize if necessary:

   • The solution provided already has a time complexity of O(n^2) since we traverse the table diagonally.
   • There is no further optimization possible for this approach.

8. Handle error cases:

   • The solution handles the case when the input string is empty or has a length of 1.
   • We assume that the input string only contains valid characters.

9. Discuss complexity analysis:

   • Time complexity: The time complexity of the solution is O(n^2) since we traverse the table diagonally.
   • Space complexity: The space complexity is O(n^2) as we create a 2D table to store the palindrome information for substrings.