Palindrome queries HackerEarth Problem

Palindrome queries | Practice Problems

Task:- Given a string str and Q queries, each query contains left index ‘l’ and right index ‘r’. For each query print whether the substring formed from ‘l’ to ‘r’ can be rearranged to form a palindrome or not.

For eg: str = “abbacd”

Q=3

1. L=1, R= 4
2. L=1, R=5
3. L=3, R=6

Answer:

1. Possible. The substring “abba” is already a palindrome.
2. Possible. The substring can be rearranged as “abcba”
3. Impossible. The substring “bacd” cannot be rearranged to form a palindrome.

Note:- The indices in query are based on 1-based indexing.

Brute Force Approach:- To check whether a string can be rearranged into a palindrome or not. We can check whether the count of elements which occurs an odd number of times in string.

If the length of string is even, all the characters must be present even number of times.

If the length of string is odd, all the characters must be present even number of times except one character.

For more detailed explanation on this refer this problem:

Game of Thrones — I HackerRank Problem

We can create a function can_be_palindrome() and call function for each substring.

The time complexity for this approach would be O( N*Q ). This is because creating the substring and checking whether it can be converted into palindrome takes linear time( O(N) ) and we do this for Q queries.

N → Length of String

Brute Force Code:-

Efficient Approach:- We can use cumulative sum-like technique to get the content (frequency of each character) of the substring. We create a list of length ’N’ and each element of this array contains an array/list of 26 integers representing the count of each letter from start of the string to a particular index.

So the i th index of this list contains content of substring from index 0 to index i.

To check whether a string can be rearranged into a palindrome, we can use the same conditions we used before.

To get the answer for queries, we first need to get the content of the substring which can be given by subtracting array at ‘r’ index from array at ‘l — 1’ index ( element by element ).

Time complexity of this approach would be O(N+Q) because for each query the answer is calculated in constant time( O(1) ).

Efficient Code:-