PrepBuddy and Strings
Difficulty
easy
Prerequisite
Strings
Problem Statement
The task is to check whether a string can be converted into Palindrome string by
changing each character of the string exactly once and it can be changed either
to the previous letter in alphabetic order or to the next one.
Explanation
To satisfy palindrome condition, first and last character should be the same,
second and second last character should be the same, third and third last
character should be the same, fourth and fourth last character should be the
same, and so on…
If we can make these pairs of characters same after applying the operation
mentioned in the problem statement, then the string is a Palindrome string.
For example, cgie , first and last character can be changed to d by increasing
character c and decreasing character e, so the string becomes dgid. Now g and
i can be changed to h using the same operation so the string becomes dhhd
which is a palindrome.
To check whether it is even possible to make a string, Palindrome string, * one
way is to check for all possible combinations * second way is to check for the
condition that character pairs mentioned above should either have difference 0
or 2.
In string cgie, first and last character have difference e−c = 101−99(ASCII) =
2, so it is possible to make them equal. Similarly, the second and second last
character has a difference of 2, so it is possible to make them equal.
In string abe, the difference between first and last character is e−a = 101−97 = 4
which is neither 0 or 2, and since each character is changed exactly once, there
is no way to make a and e equal. Therefore abe is not a palindrome string.
Time complexity
O(n)
1
Code
Java code
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t–>0) {
int len = sc.nextInt();
String str = sc.next();
boolean flag = true;
for (int i = 0; i < len / 2; i++) {
if (!(str.charAt(i) == str.charAt(len - i - 1)
|| Math.abs(str.charAt(i) - str.charAt(len -
i - 1)) == 2))
flag = false;
}
System.out.println(flag ? “YES” : “NO”);
}
}
}