PROBLEM LINK:
Author: Anita Acha George
Tester: Alex Mathew
Editorialist: Alex Mathew
DIFFICULTY:
EASY
PREREQUISITES:
OBSERVATION
PROBLEM:
Banta was talking with his best friend Santa. Santa challenged Banta that he knew many strings such that the reverses of all substrings were included in the substring itself. When Banta asked Santa to explain, Santa gave the following examples
String = “ab”
Possible substrings are “a”,“b”,“ab” but reverse of “ab” is not present in string
String = “abab”
Possible substrings are “a”, “b”, “a”, “b”, “ab”,“ba”, “ab”, “aba”, “bab”, “abab” but reverse of “abab” is not present in string
Help Banta verify Santa’s claim by writing a program which checks whether the strings spoken by Santa matches what he says
QUICK EXPLANATION:
Basically the question is asking you to check if the entered string is a palindrome.
EXPLANATION:
If for every string, the reverse string has to be present , then it means that assuming first half contains the string, the second half contains the reversed subpart. A generalisation of the task can be thought out to be to check if the string is a palindrome.
FUNCTION TO CHECK PALINDROME
bool isReversible(char str[100])
{
int i = 0, j = strlen(str)-1;
while (i < j)
{
if (str[i] != str[j])
return false;
i++;
j--;
}
return true;
}
This code runs with a complexity of O(n)
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.