Sub palindrome queries - HackerEarth

solution.py

# Question Link - https://www.hackerearth.com/practice/algorithms/string-algorithm/string-searching/practice-problems/algorithm/palindrome-queries-eefd5c23/
'''
Problem
You are given a string 
 that contains 
 lowercase alphabets. There are 
 queries of the form 
. Your task is to determine if every character in the range 
 can be arranged in such a manner that a palindromic substring for that range can be formed. If it is possible to create the palindrome substring in the provided interval, then print Possible. Otherwise, print Impossible.

Note: The original string is not changed in the process.

Input format

First line: 
 denotes the number of queries 
Second lines: String 
 of 
 lowercase English letters 
Third line: Number of queries of the 
 format 
Output format

Print 
 lines for each query. Print Possible if a palindrome substring is formed in the provided interval. Otherwise, print Impossible.

Constraints


Sample Input
4
abccab
1 3
2 3
3 3
3 5
Sample Output
Impossible
Impossible
Possible
Possible
'''

# Concept : Create Prefix sum over string for all letters 
# Now in L to R, get count of each alphabet using PF[R] - PF[L-1] 
# If in a string the number of chars with odd count are greater than 1 then we cant make it a palindrome


q = int(input())
s = input()
n = len(s)

D = { chr(i+97) : [0]*n for i in range(26)}
vis = set()
for i, val in enumerate(s):
    if not val in vis :
        vis.add(val)
        arr = D[val]
        for x in range(n):
            if s[x] == val:
                arr[x] += 1
        
        for x in range(1, n):
            arr[x] += arr[x - 1]
        
        D[val] = arr 


for _ in range(q) :
    l, r = map(int, input().split())
    l, r = l - 1, r - 1
    odd_cnt = 0
    for k in D :
        if (D[k][r] - D[k][l-1]) %2  != 0 :
            odd_cnt += 1
    if odd_cnt > 1 :
        print("Impossible")
    else:
        print("Possible")