Strings Interview Questions

Longest Palindromic Substring

Harsh

Concepts Used

Strings

Difficulty Level

Medium

Problem Statement (Simplified):

Find the longest palindromic substring in a given string and print the substring.

See original problem statement here

Test Cases:

Input:
1
findnitianhere

Output:
indni

Explanation:
In 'findnitianhere', we have total 18 palindromic substrings that are 'f','i','n','d','ndn','indni','n','i','t','iti','i','a','n','h','e','r','ere' and 'e'. Here we can see 'indni' is the largest palindromic substing with length 5. So, 'indni' is our answer.

Solving Approach :

Bruteforce Approach:

1) We can find every possible substring of the given string and then find the largest string that is palindromic in them. We print such string.
2) This approach takes two loops for finding all substrings, and a loop for checking if the substring is palindrome or not for every possible substring found. Hence time complexity for this approach is O(N^{3}).
3) We can observe that length of the string goes from 1 to 10^{3}, so this approach is inefficient for such string. We can solve this problem with a more efficient approach by referring online programming courses.

Efficient Approach:

1) Substring can be odd and even in length, so we find the longest substring in both length, and then print out the longest one.
2) For odd sized substrings, we start from a single pointer and expands both ways, and continue if both sides are equal. Once both characters i.e. in left and right are unequal or string ends, we compare the length of the current substring. If the length is higher than the current longest substring, we save the substring length and it's start and end index.
3) For even sized substrings, we initialize with two pointers i.e. left and right and expand them on both sides, and repeat the same process as in case of odd.
4) We perform this iteration for every index of the substring.

Example

  • Let's assume string S is bbbbbabbb. So we iterate over string character by character and check for both odd sized and even sized palindromes having current character as middle element.

Odd sized Palindromes : We use a pointer start, we'll iterate towards both end of start and will continue until characters on both sides does'nt match

> For i=1 :

> From above image, we can see that palindromic substring found is 'bbb' with length 3.
>
> For i=2 :

> From above image, we can see that palindromic substring found is 'bbbbb' with length 5.
>
> For i=3 :

> From above image, we can see that palindromic substring found is 'bbb' with length 3.
>
> For i=4 :

> From above image, we can see that palindromic substring found is 'b' with length 1.
>
> For i=5 :

> From above image, we can see that palindromic substring found is 'bbbabbb' with length 7.
>
> For i=6 :

> From above image, we can see that palindromic substring found is 'b' with length 1.
>
> For i=7

> From above image, we can see that palindromic substring found is 'bbb' with length 3.
>
Here we can see we find largest palindromic substring with length 7 at starting at index 2 and ending at index 8 having middle element at index i=5.

Even sized Palindromes : We use two pointers i.e. i and j for it, we'll iterate towards both ends of i and j, we will continue until characters on both sides does'nt match
>
>

> From above image, we can see that palindromic substring found is 'bbbb' with length 4.
>
>
> From above image, we can see that palindromic substring found is 'bbbb' with length 4.
>
>
> From above image, we can see that palindromic substring found is 'bb' with length 2.
>
>
> From above image, we can see that no palindromic substring is found.
>
>
> From above image, we can see that no palindromic substring is found.
>
>
> From above image, we can see that palindromic substring found is 'bb' with length 2.
>
>
> From above image, we can see that palindromic substring found is 'bb' with length 2.

Here we can see we find largest palindromic substring with length 4 which is smaller than the largest palindromic string found in odd section. So substring found in odd section is our final answer.

So our longest palindromic substring starts at index 2 and ends at 8 with size 7 and substring is 'bbbabbb'

Solutions

#include <stdio.h>

int main()
{
  int test;
  scanf("%d",&test);

  while(test--){

    char a[1001];
    scanf("%s",a);

    int longestSubstring = 1, start=0, end = 0;

    //Odd palindromic substrings
    for(int i=1; i<strlen(a); i++){
      int j= i-1, k=i;
      while( j>=0 && k<strlen(a) && a[j]==a[k] ){
        if( k-j+1 > longestSubstring){
          start = j;
          end = k;
          longestSubstring = k-j+1;
        }
        j--;
        k++;
      }
    }

    //Even palindromic substring
    for(int i=0; i<strlen(a); i++){
      int j= i-1, k=i+1;
      while( j>=0 && k<strlen(a) && a[j]==a[k] ){
        if( k-j+1 > longestSubstring){
          start = j;
          end = k;
          longestSubstring = k-j+1;
        }
        j--;
        k++;
      }
    }

    for(int i=start; i<=end; i++ )
      printf("%c",a[i]);
    printf("\n");

  }
  return 0;
}


#include <bits/stdc++.h>
using namespace std;

int main()
{
  int test;
  cin>>test;

  while(test--){

    string a;
    cin>>a;

    int longestSubstring = 1, start=0, end = 0;

    //Odd palindromic substrings
    for(int i=1; i<a.length(); i++){
      int j= i-1, k=i;
      while( j>=0 && k<a.length() && a[j]==a[k] ){
        if( k-j+1 > longestSubstring){
          start = j;
          end = k;
          longestSubstring = k-j+1;
        }
        j--;
        k++;
      }
    }

    //Even palindromic substrings
    for(int i=0; i<a.length(); i++){
      int j= i-1, k=i+1;
      while( j>=0 && k<a.length() && a[j]==a[k] ){
        if( k-j+1 > longestSubstring){
          start = j;
          end = k;
          longestSubstring = k-j+1;
        }
        j--;
        k++;
      }
    }

    for(int i=start; i<=end; i++ )
      cout<<a[i];
    cout<<endl;

  }
  return 0;
}


import java.util.*;
import java.io.*;
import java.lang.Math;

public class Main {
public static void main(String args[]) throws IOException {

    Scanner sc= new Scanner(System.in);
    int test = sc.nextInt();
    while(test != 0){
        String a = sc.next();

        int longestSubstring = 1, start=0, end = 0;

        //Odd palindromic substrings
        for(int i=1; i<a.length(); i++){
          int j= i-1, k=i;
          while( j>=0 && k<a.length() && a.charAt(j)==a.charAt(k) ){
            if( k-j+1 > longestSubstring){
              start = j;
              end = k;
              longestSubstring = k-j+1;
            }
            j--;
            k++;
          }
        }

        //Even palindromic substrings
        for(int i=0; i<a.length(); i++){
          int j= i-1, k=i+1;
          while( j>=0 && k<a.length() && a.charAt(j)==a.charAt(k) ){
            if( k-j+1 > longestSubstring){
              start = j;
              end = k;
              longestSubstring = k-j+1;
            }
            j--;
            k++;
          }
        }

        for(int i=start; i<=end; i++ )
          System.out.print(a.charAt(i));

        System.out.println();
        test--;
    }
  }
}

Space Complexity of this approach would be O(1).

Previous post Maximum Sum Rupees
Next post Form the Largest Number

Leave a Reply

Your email address will not be published. Required fields are marked *

Close

Related Post