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(N3).
3) We can observe that length of the string goes from1
to 10(N3), so this approach is inefficient for such string. We can solve this problem with a more efficient approach.
Efficient Approach:
1) Substring can be
odd
andeven
in length, so we find the longest substring in both length, and then print out the longest one.
2) Forodd
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’sstart
andend
index.
3) Foreven
sized substrings, we initialize with two pointers i.e.left
andright
and expand them on both sides, and repeat the same process as in case ofodd
.
4) We perform this iteration for every index of the substring.
Example
- Let’s assume string
S
isbbbbbabbb
. So we iterate over string character by character and check for bothodd
sized andeven
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--; } } }
[forminator_quiz id="1268"]
Space Complexity of this approach would be O(1).
This article tried to discuss Strings. Hope this blog helps you understand and solve the problem. To practice more problems on Strings you can check out MYCODE | Competitive Programming.