Table of Contents

## Given a string, write a function that will find the longest palindromic substring

### Example

**INPUT **

s = “ebcdcbn”

**OUTPUT**

“bcdcb” is the longest palindromic substring

### Method 1(Brute Force) :

In this method we will pick all the substrings and check whether the substring is palindrom or not

**Time Complexity: O(n^3)**

## Algorithm

**1.** Simply run three loops

**2.** In the outer loop pick all substrings one by one by fixing the corner elements

**3.** In the inner loop check whether the picked substring is palindrome or not

### Method 2(Dynamic Programming) :

In this method the main idea is to store the results of subproblems

**Time Complexity : O(n^2)**

**Space Complexity : O(n^2)**

## Algorithm

**1.** Create a two diemensional Boolean array, ie table[n][n], where table[i][j] is true if the string from i index to j index is a palindrome

**2.** All the substrings of length 1 are palindromes, so make table[i][i] TRUE

**3.** For all the substrings of length 2, if the first and second character are same then it is a palindrome ie, if s[i] = s[i+1] make table[i][i+1] = true

**4.** Now, check for substrings having length more than 2.

The Condiiton is, table[i][j] is true if the value of table[i+1][j-1] is true and s[i] is same as s[j] ie, for above example “bcdcb” is a palindorme because “cdc” is a palindrome and ‘b’ == ‘b’ .

## C++ Program

#include <bits/stdc++.h> using namespace std; //It will take the string and prints the longest palindromic substring //and its length void printLPSS( char *s ) { //finding the length of given string int n = strlen(s); //Table table[i][j] is true if the string from i index to j index is a palindrome bool table[n][n]; //Initializing all contents of the table to 0 memset(table, 0, sizeof(table)); // All substrings of length 1 are palindromes int maxLength = 1; for (int i = 0; i < n; ++i) table[i][i] = true; // check for sub-string of length 2. int start = 0; for (int i = 0; i < n-1; ++i) { if (s[i] == s[i+1]) { table[i][i+1] = true; start = i; maxLength = 2; } } // Check for lengths greater than 2. k is length // of substring for (int k = 3; k <= n; ++k) { // Fix the starting index for (int i = 0; i < n-k+1 ; ++i) { // Get the ending index of substring from // starting index i and length k int j = i + k - 1; // checking for sub-string from ith index to // jth index iff s[i+1] to s[j-1] is a // palindrome if (table[i+1][j-1] && s[i] == s[j]) { table[i][j] = true; if (k > maxLength) { start = i; maxLength = k; } } } } //Printing the longets palindromic substring int end = start + maxLength - 1; cout<<"Longest palindrome substring is "; for( int i = start; i <= end; ++i ) { cout<<s[i]; } cout<<endl; //Length of the above longest palindromic substring cout<<maxLength<<endl; } int main() { char s[] = "ebcdcbn"; printLPSS(s); return 0; }

Try It

### Method 3

In this method the main idea is to generate all even length and odd length palindromes and keep track of longest palindrome

**Time Complexity: O(n^2)**

**Space Complexity: O(1)**

## Algorithm

**Traverse through the given string**

**1.** For the odd length palindrome, Fix the centre and expand in both directions for longer palindromes

Example for odd length palindorme, s = “ebcdcbn”

Traverse the string with low = i-1 and high = i+1, where initial i =1

At some point we stop at low = ‘c’ and high = ‘c’, low = high. Expand on both directions

Now, low = ‘b’ and high = ‘b’. low = high

Therfore the longest palindrome is “bcdcb”

**2.** For the even length palindrome, there will be no centre and will expand on both directions for longer palindromes

Example for even length palindrome, s = “ebccbn”

Traverse the string with low = i-1 and high = i

At some point we stop at low = ‘c’ and high = ‘c’, low = high. Expand on both directions

Now, low = ‘b’ and high = ‘b’. low = high

Therfore the longest palindrome is “bccb”

## C++ Program

#include <bits/stdc++.h> using namespace std; //It will take the string and prints the longest palindromic substring //and its length void printLPSS(char *s) { int maxLength = 1; // The result (length of LPS) int start = 0; int n = strlen(s); int low, high; // One by one consider every character as center point of // even and length palindromes for (int i = 1; i < n; ++i) { // Find the longest odd length palindrome with center // point as i low = i - 1; high = i + 1; while (low >= 0 && high < n && s[low] == s[high]) { if (high - low + 1 > maxLength) { start = low; maxLength = high - low + 1; } --low; ++high; } // Find the longest even length palindrome with no centre point low = i - 1; high = i; while (low >= 0 && high < n && s[low] == s[high]) { if (high - low + 1 > maxLength) { start = low; maxLength = high - low + 1; } --low; ++high; } } //Printing the longest palindromic substring int end = start + maxLength - 1; cout<<"Longest palindrome substring is "; for( int i = start; i <= end; ++i ) { cout<<s[i]; } cout<<endl; //Length of the above longest palindromic substring cout<<maxLength<<endl; } int main() { char s[] = "ebccbn"; printLPSS(s); return 0; }

Try It