Longest Palindrome is String

[om-ganesh]

Given a string S, find the longest palindromic substring in S. Substring of string S: S[ i . . . . j ] where 0 ≤ i ≤ j < len(S). Palindrome string: A string which reads the same backwards. More formally, S is palindrome if reverse(S) = S. Incase of conflict, return the substring which occurs first ( with the least starting index ).

NOTE: Required Time Complexity O(n2).

Input: The first line of input consists number of the testcases. The following T lines consist of a string each.

Output: In each separate line print the longest palindrome of the string given in the respective test case.

Example: Input: 1 aaaabbaa

Output: aabbaa

https://practice.geeksforgeeks.org/problems/longest-palindrome-in-a-string/0

[om-ganesh]

Discussion 20200922:

[hasanpoet]

1. Let's do it using loop
2. Let's do it using Recursion as well

Compare the two solution and understand generic conversion between looping and recursion

[om-ganesh]

Use sliding window with dynamic programming approach:

[hasanpoet]