Longest Palindromic Substring

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 *