Given a string s of length n, the task is to find the longest palindromic substring in it.
Incase of conflict, return the substring with least starting index).
Input: "aaaabbaa"
Output: aabbaa
Input: "abc"
Output: a
Solutions
Method 1: Brute-force - O(n^3)
One naive approach to solving the problem is to generate all possible substrings of the given string and print the length of the longest substring, which is also a palindrome.
But this solution takes O(n^3) time, where n is the length of the given string.
Complexity
The time complexity of this solution is O(n^3).
In addition, O(n) auxiliary space was also used.
Method 2: DP (Bottom Up)
One naive approach to solving the problem is to generate all possible substrings of the given string and print the length of the longest substring, which is also a palindrome. But this solution takes O(n^3) time, where n is the length of the given string.
This O(n^3) solution can be optimized by storing results of Overlapping Subproblems (Dynamic Programming).
In this solution, we need to maintain a boolean table[n][n] that is filled in a bottom-up manner.
The value of table[i][j] is "true" if the substring from "i th" to "j th" index is a palindrome, otherwise false.
We know that a single-character string is always a palindrome of length one, i.e., t[i][j] = true, where i=0, j=0.
We also know that a two-character string is a palindrome if both characters are equal, i.e. t[i] [j] = true, where i = 0 and j = 1.
Now the only task left is to check for sub-strings of length 3 or more.
A string with 3 or more characters is a palindrome if the corner characters of the string are equal and the middle sub-string is also a palindrome, i.e. s.charAt(i) == s.charAt(j) && t[i+1][j-1] == true.
Complexity
The time complexity of this solution is O(n^2).
In addition, O(n^2) auxiliary space was used by the table.