Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!
Recursion Interview Programming

Longest Palindromic Substring

Shaily

Last Updated on March 31, 2022 by Ria Pathak

CONCEPTS USED:

Recursion,Dynamic programming.

DIFFICULTY LEVEL:

Hard

PROBLEM STATEMENT (SIMPLIFIED):

You are given a string str, find the longest palindromic substring in str.
Longest Palindromic Substring of string str:LPS[i…j], where 0<=i<=j< len(LPS)

Palindrome string: LPS is palindrome if reverse(LPS) =LPS
If multiple LPS is the same then return the Longest Palindromic Substring which occurs first ( with the least starting index ).

See original problem statement here

For Example :

Input
3
aaa
bbabb
baa

Output
aaa
bbabb
aa

SOLVING APPROACH:

Brute Force:

The simple approach is to check each substring whether the substring is a palindrome or not. To do this first, run three nested loops, the outer two loops pick all substrings one by one by fixing the corner characters, the inner loop checks whether the picked substring is palindrome or not.

Time complexity: O(n3)
Three nested loops are needed to find the longest palindromic substring in this approach, so the time complexity is O(n3)
Auxiliary complexity: O(1).
As no extra space is needed.

OPTIMIZATION:

To improve over the brute force solution, we first observe how we can avoid unnecessary re-computation while validating palindromes. Consider the case "ababa". If we already knew that "bab" is a palindrome, it is obvious that "ababa" must be a palindrome since the two left and right end letters are the same.


P(i,j) = {true,}if the substring Si …Sj is a palindrome;
        {false,}otherwise

Therefore,
P(i, j) =(P(i+1,j−1) and Si==Sj)

The base cases are:
P(i, i) = true
P(i, i+1) = (Si==Si+1 )

This yields a straight forward DP solution, which we first initialize the one and two letters palindromes, and work our way up finding all three letters palindromes, and so on…

SOLUTIONS:

#include 

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=0 && k longestSubstring){
          start = j;
          end = k;
          longestSubstring = k-j+1;
        }
        j--;
        k++;
      }
    }

    //Even palindromic substring
    for(int i=0; i=0 && k 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 
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=0 && k longestSubstring){
          start = j;
          end = k;
          longestSubstring = k-j+1;
        }
        j--;
        k++;
      }
    }

    //Even palindromic substrings
    for(int i=0; i=0 && k longestSubstring){
          start = j;
          end = k;
          longestSubstring = k-j+1;
        }
        j--;
        k++;
      }
    }

    for(int i=start; i<=end; i++ )
      cout<
						 
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=0 && k longestSubstring){
              start = j;
              end = k;
              longestSubstring = k-j+1;
            }
            j--;
            k++;
          }
        }

        //Even palindromic substrings
        for(int i=0; i=0 && k 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--;
    }
  }
}

for _ in range(int(input())):

	a = list(input())
	longestSubstring, start, end = 1, 0, 0

	for i in range(1, len(a)):

		j = i - 1
		k = i

		while( j >= 0 and k < len(a) and a[j] == a[k] ):

			if( k - j + 1 > longestSubstring):

				start = j
				end = k
				longestSubstring = k - j + 1
				
			j -= 1
			k += 1

	for i in range(len(a)):
		
		j = i - 1
		k = i + 1
		
		while( j >= 0 and k < len(a) and a[j] == a[k] ):
			
			if( k - j + 1 > longestSubstring):
			
				start = j
				end = k
				longestSubstring = k-j+1
			
			j -= 1
			k += 1
		
	print(*a[start:end + 1], sep = "")

Space complexity: O(n2). It uses O(n2) space to store the table.

[forminator_quiz id="2335"]

This article tried to discuss Recursion, Dynamic programming. Hope this blog helps you understand and solve the problem. To practice more problems on Recursion,Dynamic programming you can check out MYCODE | Competitive Programming.

Leave a Reply

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

Close

Related Post