Finding the Longest Palindrome in a String

Hey ! Finding the longest palindrome in a string is one of the most commonly asked interview questions if you're aspiring to be a software development engineer. In this post we will be dealing with an optimal solution for this problem. There are two ways to solve the problem. They are listed down as follows.

Brute Force 

  1. Initialise result to an empty string.
  2. Loop through each character of the string.
  3. Find for a matching character.
  4. See if the string bounded by the two characters form a palindrome. If they do then check if the length of this string is greater than the string in result variable. If else assign the string to result.
This is an obvious solution for the problem but this is a brute force approach and is the least efficient of all the approaches. The main pitfall being the repeated checking of palindromic strings. To overcome this we can go for a dynamic approach which is discussed below.

Dynamic Approach

This is based on the concept that if the string asasa has to be a palindrome then the string sas must be a palindrome. In this approach we maintain a boolean table of size n x n, where n is the length of the string. If the cell (i, j) of the table has a value 1 then the string bound by the indices i and j (i.e. s[i]....s[j]) is a palindrome and vice versa. The algorithm is as follows

  1. Initialise a boolean table of size n x n to 0, where n is the length of the string.
  2. Check for the following two basis steps.
    1. Change the values of the leading diagonal to 1 as a single character always forms a palindrome.
    2.  Loop through the string and check if the string bound by i and i+1 forms a palindrome and if it does change the value of (i, i+1) in the table to 1.
  3. We have now checked for a single character and two characters. Now run a loop (i loop) from 3 to n-1.
  4. Run an inner loop (j loop) which would loop through the characters of the given string.
  5. To check if the string bound by j and j+i is a palindrome we have to check if s[j] and s[j+i] are equal (as a palindrome always starts and ends with the same character) and if table[j][j+i-1] is 1 (as the inner string must be a palindrome for the current string to be a palindrome).
  6. Change the value of table[j][j+i] to 1 if the conditions are satisfied. 
  7. If the string is a palindrome then update the result variable to the current string.
Code (C++)


  1. #include <iostream>  
  2. #include <string>  
  3.   
  4. using namespace std;  
  5.   
  6. string palindrome(string a){  
  7.       
  8.     int n;  
  9.     n = a.length();  
  10.     int table[n][n];  
  11.     int max_length = 1, start = 0;  
  12.       
  13.     //initialise the values of table to 0  
  14.     for(int i = 0; i < n; i++){  
  15.         for(int j = 0; j < n; j++)  
  16.             table[i][j] = 0;  
  17.     }  
  18.       
  19.     //base case - single character  
  20.     for(int i = 0; i < n; i++){  
  21.         table[i][i] = 1;  
  22.     }  
  23.       
  24.     //base case - two characters  
  25.     for(int i = 0; i < n-1; i++){  
  26.         if(a[i] == a[i+1]){  
  27.             table[i][i+1] = 1;  
  28.             start = i;  
  29.             max_length = 2;  
  30.         }  
  31.     }  
  32.       
  33.     //more than two characters  
  34.     for(int i = 3; i <= n; i++){  
  35.         for(int j = 0, x = i - 1; x <= n; j++, x++){  
  36.             if(a[j] == a[x] && table[j+1][x-1] == 1){  
  37.                 start = j;  
  38.                 max_length = i;  
  39.                 table[j][x] = 1;  
  40.             }  
  41.         }  
  42.     }  
  43.       
  44.     //getting the substring  
  45.     string res = a.substr(start, max_length);  
  46.       
  47.     return res;  
  48.       
  49. }  
  50.   
  51. int main(int argc, const char * argv[]) {  
  52.       
  53.     string a;
  54.     cin>>a;
  55.     cout<<"Longest Palindrome : "<<palindrome(a)<<"\n";  
  56.     return 0;  
  57. }  


Output


Feel free to post your solution to the problem in the comments section below. Happy Coding :)

Comments

Popular posts from this blog

Finding a Single Number amongst Repeated Numbers [Repeated Twice]

Finding the Longest Path From One Point To Another - Dynamic Programming