PROBLEM LINK:
Author: Arush Nagpal
Tester: Rahul Johari
DIFFICULTY:
EASY.
PREREQUISITES:
Strings, Palindrome
PROBLEM:
Given three classes A,B and C for strings, we need to determine if a given string belongs to class C or not.
EXPLANATION:
Already defined -
Class A : A sequence of letters that read the same forward and backward - Palindrome.
Class B : A string of class B can be converted to class A type by changing exactly one letter to a different letter.
Class C : A string of class C is one that is formed by concatenating 2 strings of class B together.
We can observe that Class A string is a palindrome. Now to check a class B string, we use two pointers, one to traverse from the beginning and the other to traverse from the end and count the number of unequal characters. Determine whether the word found in string (from first index to last index) is a class B string or not. Return 1 if there is exactly one difference or an odd length else returns 0.
One solution can be bruteforce, in which you break the string into 2 parts and check for both of them separately. But it will take more time.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.