PROBLEM LINK:
Author: Kamal Verma
Tester: Kamal Verma
Editorialist: Ashish Ahuja
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Palindrome,
String Processing,
String Manipulation
PROBLEM:
A typical problem of string manipulation and use of palindromes.
QUICK EXPLANATION:
A predefined notation is used to map the strings and then,using the notation format the number of palindrome sub-strings in the string is found out .
EXPLANATION:
The problem demands an analytical approach and good understanding of palindromes. There are various ways to solve this problem, one of which is explained here -
The solution modules are aimed at solving different parts of the problem -
In one module(method), the string notation is first expanded to generate the actual string, so that the analysis of the situation becomes easier.This module generates the string for the solve() module to find out the sub-strings. This is done by using simple mathematics to analyse the length of the string expected, and then producing the output to the solve method.
void expand(int len)
{
- - - -
int expand;
for(i=2;i(<)n;i++)
{
mirror=2*center-i;
- - - -
if(diff>0)
//do-something
if(expand==1)
//do-something
}
- - - -
}
The second module then focuses on solving the palindrome mystery by comparing each possible sub-string to its reverse string.This module takes the output of the expand function , to evaluate the palindromes in the given string and at last return the number count of the palindromes discovered.
void solve()
{
int len=strlen(str),i;
for(i=0;i(<)len;i++)
- - - -
expand(len);
- - - -
sum[0]=arr[0];
- - - -
for(int i=0;i(<)len;i++)
{
//do-something
}
printf("%lld\n", ans);
}
The output from both the modules is combined in the main function to display the required output.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.