PROBLEM LINK
PROBLEM STATEMENT
The research for the Corona Virus is going on in the Secret Research Facility at Wuhan. China is desperately working day and night to find the cure to free its citizens from the virus. Ishita, the lead scientist who came specially from India to help China combat this virus is very close to finding the cure.
She is now looking at the DNA sequence of the virus to find a pattern which she can manipulate to create the antidote. She recognises that finding a palindrome between a given set of indices will help her find the cure. But the indices change so rapidly that she needs to start working again. She calls you to help her with this problem.
She assigns you the work to tell her if she can manipulate the substring formed from the indices to make a palindromic string. She can then use this palindromic string and combine this with the virus to create the antidote.
Note: DNA Sequence consists of only lowercase letters.
SOLUTION
Make a 2D table let’s call it dp. i.e. dp[|S|][26] . Now mark the position of the index in the dp array, and for making them cumulative for every index from ’ a ’ to ’ z '.
Now our task is to find the number of odd occurring characters in the range of Query [L, R] . And this could be done using the prefix sum type technique for every index from 0 to 25 i.e. from a to z .
if the count of odd characters in the given range is <= 1 the string can be formed palindrome else it can’t be formed.
SOLUTION CODE
import java.util.*;
import java.io.*;
class TestClass {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(bf.readLine());
String word = bf.readLine();
int arr[][] = new int[word.length() + 1][26];
for (int i = 1; i <= word.length(); i++) {
char x = word.charAt(i - 1);
arr[i][x - 97]++;
}
for (int i = 1; i <= word.length(); i++) {
for (int j = 0; j < 26; j++) {
arr[i][j] += arr[i - 1][j];
}
}
String strNum[];
mainLoop:
while (t > 0) {
strNum = bf.readLine().split("\\s");
int x = Integer.parseInt(strNum[0]);
int y = Integer.parseInt(strNum[1]);
boolean flag = false;
for (int i = 0; i < 26; i++) {
int a = arr[x - 1][i];
int b = arr[y][i];
if (((b - a) & 1) != 0) {
if (flag) {
System.out.println("Impossible");
t--;
continue mainLoop;
} else {
flag = true;
}
}
}
System.out.println("Possible");
t--;
}
}
}