**Find longest palindrome in a string. **

Brute Force: N^3

Below Method by Dynamic Programming is N^2. Video for below method:

https://www.youtube.com/watch?v=obBdxeCx_Qs

There is another algorithm called Mancher’s Algorithm which is in linear time.

**Note that here since we are dealing with single string we just need to populate top triangle of matrix. In longest substring since we were dealing with 2 strings we populated the whole matrix. **

$str = "BANANA"; $len = strlen($str); $matrix = array(); $palindromeBegins = 0; $max = 1; // single letter palindromes for ($i=0; $i < $len; $i++) { $matrix[$i][$i] = 1; }; // 2 character palindromes for ($i=0; $i < $len-1; $i++) { if ($str[$i] == $str[$i+1]) { $matrix[$i][$i+1] = 1; $max = 2; $palindromeBegins = $i; } } // 3 character and above for ($curr_len=3; $curr_len <= $len ; $curr_len++) { for ($i=0; $i < $len-$curr_len+1; $i++) { $j = $i+$curr_len-1; // 1. first and last chars should match // 2. rest of string from previous calculations should be a palindrome if (($str[$i] == $str[$j]) && ($matrix[$i+1][$j-1] == 1)) { $matrix[$i][$j] = 1; $max = $curr_len; $palindromeBegins = $i; } } } echo "Max Palindome: $max\n"; echo "Palindrome: " . substr($str, $palindromeBegins, $max); echo "\n";

Another approach:

http://krenzel.org/articles/longest-palnidrome