Palindrome queries

3.7

9 votes
Algorithms, String Manipulation
Problem

You are given a string S that contains n lowercase alphabets. There are Q queries of the form [L,R]. Your task is to determine if every character in the range [L,R] 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: Q denotes the number of queries 
  • Second lines: String S of n lowercase English letters 
  • Third line: Number of queries of the [L,R] format 

Output format

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

Constraints

|s|105|Q|105|s|1051LRn

Sample Input
4
abccab
1 3
2 3
3 3
3 5
Sample Output
Impossible
Impossible
Possible
Possible
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In this case We can't make string palindrome if the interval is between [1, 3], [2, 3]. But we could make palindrome for the individual characters so it's possible for [3, 3].

Also for the case [3, 5] it's possible by shuffling the substring cca as cac so it can be formed as a palindrome.

Editor Image

?