Question: Write a function to find the longest palindromic substring in a given string. A palindromic substring is a string that remains the same when its characters are reversed.

Implement a function longestPalindrome(s: str) -> str, where:

• s is a non-empty string consisting only of lowercase English letters.
• The function should return the longest palindromic substring of s.

Example:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer, but "bab" is longer.

Input: s = "cbbd"
Output: "bb"

Input: s = "a"
Output: "a"

Note: You may assume that the maximum length of s is 1000.

Answer:

The problem can be solved using dynamic programming. We will define a 2D boolean array dp, where dp[i][j] will be True if the substring from index i to j is a palindrome, otherwise it will be False.

The idea is as follows:

• Initialize dp array of size n x n, where n is the length of the input string.
• All substrings of length 1 are palindromes, so we set dp[i][i] to True for all i.
• For substrings of length 2, if the two characters are the same, then it is a palindrome.
• For substrings of length greater than 2, if the first and last characters are the same and the substring between them is a palindrome, then it is also a palindrome.
• We keep track of the longest palindromic substring found so far and update it whenever we find a longer palindrome.

Here is the step-by-step detailed explanation of the solution:

1. Define the function longestPalindrome(s: str) -> str to take a single input string s and return the longest palindromic substring.
2. Initialize variables start and end as 0 and 0, respectively. These variables will store the starting and ending indices of the longest palindromic substring found so far.
3. Initialize a boolean array dp of size n x n, where n is the length of the input string s. All elements in dp are initially set to False.
4. Iterate over the string s using a for loop from i = n - 1 to 0 (backwards).
5. Inside the first loop, iterate again over the string s using a nested for loop from j = i to n.
6. Inside the nested loop, set dp[i][j] to True if one of the below conditions is met:
   • s[i] == s[j] and (j - i <= 2) (handles substrings of length 1 and 2).
   • s[i] == s[j] and dp[i+1][j-1] is True (handles longer substrings).
7. If dp[i][j] is True and (j - i + 1) > (end - start + 1), update start and end with the current indices i and j.
8. Finally, return the longest palindromic substring using s[start:end+1].

Here is the implementation of the solution in Python:

def longestPalindrome(s: str) -> str:
    n = len(s)
    start, end = 0, 0
    dp = [[False] * n for _ in range(n)]

    for i in range(n - 1, -1, -1):
        dp[i][i] = True
        for j in range(i, n):
            if s[i] == s[j] and (j - i <= 2 or dp[i+1][j-1]):
                dp[i][j] = True
                if (j - i + 1) > (end - start + 1):
                    start, end = i, j
    
    return s[start:end+1]

The time complexity of this solution is O(n^2) and the space complexity is O(n^2), where n is the length of the input string s.