\nThe simple approach is to check each substring whether the substring is a palindrome or not. To do this first, run three nested loops, the outer two loops pick all substrings one by one by fixing the corner characters, the inner loop checks whether the picked substring is palindrome or not.<\/p>\n
Time complexity<\/strong>: O(n3<\/sup>)
\nThree nested loops are needed to find the longest palindromic substring in this approach, so the time complexity is O(n3<\/sup>)
\nAuxiliary complexity<\/strong>: O(1).
\nAs no extra space is needed.<\/p>\n<\/blockquote>\nOPTIMIZATION:<\/h3>\n\nTo improve over the brute force solution, we first observe how we can avoid unnecessary re-computation while validating palindromes. Consider the case "ababa". If we already knew that "bab" is a palindrome, it is obvious that "ababa" must be a palindrome since the two left and right end letters are the same.<\/p>\n<\/blockquote>\n
\nP(i,j) = {true,}if the substring Si \u2026Sj is a palindrome;\n {false,}otherwise\n\nTherefore,\nP(i, j) =(P(i+1,j\u22121) and Si==Sj)\n\nThe base cases are:\nP(i, i) = true\nP(i, i+1) = (Si==Si+1 )<\/code><\/pre>\nThis yields a straight forward DP solution, which we first initialize the one and two letters palindromes, and work our way up finding all three letters palindromes, and so on…<\/p>\n
SOLUTIONS:<\/h3>\n
\t\t\t\t\t\t
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1648726077068-Longest%20Palindromic%20Substring.png\")
<\/p>\n