Given a **O(n**^{2}) runtime.

**Examples : **

`String`

, write a method - `longestPalSubstr`

that finds and returns the longest substring which is also a Palindrome. Try and accomplish this in at most "bccb" => "bccb"

"bccd" => "cc"

"bccc" => "ccc"

Need a **hand?** Try out these hints, one at a time.

The brute force solution to this problem is relatively simple - but gives us a time complexity of O(n^{3}). If you want to try that out first - go for it! But later, think about using the solutions to previous problems to optimize the runtime. Consider this scenario :

Given a String "abba", "**a**bb**a**" is a palindrome if and only if "**bb**" is a palindrome and the two characters at the ends (in this case, "a") are the same. This hint strongly suggests that a Dynamic Programming solution to this problem is possible. If you dig deeper, you can prove that this problem has an **optimal sub-structure** and is comprised of **repeating subproblems**.

Given a String "abba", "

1) Create a 2D memo pad -

boolean[][] memo = new boolean[len][len]where

`len`

is the String's length. We'll use this memo pad to denote positions on the `String`

, and whether or not the substring between the two positions is a palindrome. In particular, `memo[start][finish]`

is `true`

if the `String`

is a palindrome between the indices `start`

and `finish`

.2) Create 2 variables that will be laters used to obtain the substring -

int maxSubstrLen = 1;

int maxSubstrStartIndex = 0;

3) Since each character in the string can be thought of as a palindromic substring, mark the diagonal on the matrix as

`true`

: for(int i = 0; i < len; i++){

memo[i][i] = true;

}

4) Do the same for substrings of length 2 so that we have enough data to perform a bottom up traversal :

for(int i = 0; i < len-1; i++){

if(str.charAt(i) == str.charAt(i+1)){

memo[i][i+1] = true;

maxSubstrLen = 2;

maxSubstrStartIndex = i;

}

}

5) Now use the memo array to check for substrings of length > 2. The check for palindromicity will look like this :

if(memo[i+1][j-1] && str.charAt(i) == str.charAt(j)){

memo[i][j] = true;

maxSubstrLen = l;

maxSubstrStartIndex = i;

}

That is, the memo pad is used to look up if the interior boundary is a palindrome. If true, then you check the boundary characters, and if they are the same, update the variables accordingly. That check can be summarized by this if condition -

if(memo[i+1][j-1] && str.charAt(i) == str.charAt(j))

6) Return the substring -

return str.substring(maxSubstrStartIndex, maxSubstrStartIndex + maxSubstrLen);

public String longestPalSubstr(String str){ }

**C**

**Java**

**Python**