Prerequisites :- None
Problem :- You are given an integer N the length of a string and a string S.
Print the maximum length of a palindromic substring and the maximum palindromic substring.
Explanation :- The maximum value of N given to us is 5000. Therefore we can just create all the substrings of the given string and check whether they are palindromes or not. This works because there can be at most 5000 * 5000 => 25 * 10^6 substrings, which a computer can handle within a second. This approach is called brute force.
Algorithm : -
Find all possible substrings for the given string.
Check whether the given substring is palindrome or not.
If the given substring is palindrome, check whether the length of the given substring is greater than the previous palindrome’s length.
If the length is greater, then store the substring.
For better understanding you can refer to IARCS Editorial
C++ Solution :-
#include <bits/stdc++.h>
using namespace std;
bool check(string &sub){
int start = 0;
int end = sub.length()-1;
while(start<end){
if(sub[start]!=sub[end]){
return false;
}
start++;
end--;
}
return true;
}
int main() {
int n;
cin>>n;
string s;
cin>>s;
int maxLength = 0;
string subword = "";
for(int i=0;i<n;i++){
for(int j=i;j<n;j++){
string sub = s.substr(i,j-i+1);
if(check(sub)){
int length = sub.length();
if(length>maxLength)
{
maxLength = length;
subword = sub;
}
}
}
}
cout<<maxLength<<"\n";
cout<<subword<<"\n";
}