Longest Palindromic Substring

Longest Palindromic Substring

In the longest palindromic substring problem we have to find the length of longest substring of the given string which is a palindrome. It is a famous interview question asked in many coding interviews as well as coding rounds. In this article, we will be explanation solution with c++ code.


Longest Palindromic Substring Problem Description

Longest Palindromic Substring Problem Description

In this problem we are given a input string consisting of english alphabets. We have to return the length a longest palindromic substring possible. A substring is a string that is formed by removing any number of characters (including 0) from the input string from front or back.


  • Single line input containing an input string.


  • Longest length required.

Longest Palindromic Substring Solution

The problem is similar to longest palindromic substring with little changes.


  • Create a dp table (boolean type) where if dp[i][j] is true this implies substring[i…j] is a palindrome.
  • The dp transitions will be –

if(s[i] == s[j] && substring s[i+1…j-1] is palindrome)

dp[i][j] = true (ie it also palindrome)

  • We will fill base case ie mark all 1 character length substrings in dp table as palindrome.
  • We will iterate for all possible lengths of substrings and use above formulae.

Time & Space Complexity – O(N*N), where N = length of input string.

Longest Palindromic Substring Problem Breakdown


#include <bits/stdc++.h>
using namespace std;
int f(string s)
    int n = s.length();
    bool dp[n][n];

    // Initializing dp table
    for (int i = 0i < ni++)
        for (int j = 0j < nj++)
            dp[i][j] = false;

    int ans = 1;

    // All single characters are palindromes
    for (int i = 0i < ni++)
        dp[i][i] = true;

    for (int length = 2length <= nlength++)
        for (int i = 0i <= n – lengthi++)
            int j = i + length – 1;
            if (length == 2
                if (s[i] == s[j])
                    dp[i][j] = true;
                    For substring[i…j]
                        and substring[i+1…j-1] is also a palindrome
                        => substring[i…j] is also a palindrome 
                if (s[i] == s[j] && dp[i + 1][j – 1])
                    dp[i][j] = true;

            if (dp[i][j])
                ans = max(anslength);

    return ans;
int main()
    string s;
    cin >> s;

    cout << f(s<< endl;
    return 0;


Explanation - abcdcba is the longest palindromic substring.