Find the longest palindromic subsequence using dynamic programming.

Our solution finds the longest palindromic substring by expanding around potential centers in the input string. For each character in the string, we consider it as the center of a palindrome and expand outwards to determine the maximum length of the palindrome centered at that position. We repeat this for both odd-length and even-length palindromes.

• For each character, we use a helper function expandAroundCenter that takes two indices (left and right) and expands outwards as long as the characters at these indices are equal and within the bounds of the string.
• We calculate the lengths of palindromes centered at the current character (odd-length palindromes) and between the current character and the next one (even-length palindromes).
• We track the starting and ending indices of the longest palindromic substring found so far.

By comparing the lengths of the palindromes found in each iteration, we can determine the longest palindromic substring.

The use of expansion around centers ensures that we examine all potential palindromes efficiently.

Time Complexity: The solution has a time complexity of O(n^2), where n is the length of the input string. This is because, for each character in the string, we potentially expand outwards in both directions, resulting in quadratic time complexity in the worst case.

Space Complexity: The solution uses O(1) space beyond the input string. The only extra space used is for a few variables, making it very space-efficient.