Longest Palindromic Substring
Today we will discuss a common problem. The problem is, you are given a string S, you have to find the longest palindromic substring in S. For example, S = abcbsd, here our desired answer is bcb with length 3. Solution: This problem can be solved in many ways. One of them is DP solution and another is Expand Around Center. DP: DP solution is a very straight cut solution. We go through all the substrings of the main string S and check each substring is palindrome or not and find the longest substring if it is palindrome. Here we do DP in the palindrome checking part. Here is the Code. Complexity O(n^2) . #include<bits/stdc++.h> using namespace std ; string s ; int dp [ 1005 ] [ 1005 ] ; ///dp[l][r] means is substring s[l...r] is a palindrome or not int isPalindrome ( int left, int right ) { if ( left >= right ) return 1 ; if ( dp [ left ] [ right ] ! = - 1 ) return dp [ left ] [ right ] ; int result = 0 ; if ( s [ left ]