K – Magical String codechef solution- You have been given a string SS of size NN which consists of uppercase characters only. A KK-Magical String is a string in which the longest non – decreasing subsequence is of size exactly KK. You have been given QQ queries where each query is in the form L,R,L,R, and KK. For each query, check whether substring from index LL to index RR can be converted into a KK-Magical String or not by rearranging its characters and print the final rearranged string too.

K – Magical String solution codechef

You have been given a string SS of size NN which consists of uppercase characters only. A KK-Magical String is a string in which the longest non – decreasing subsequence is of size exactly KK.

You have been given QQ queries where each query is in the form L,R,L,R, and KK. For each query, check whether substring from index LL to index RR can be converted into a KK-Magical String or not by rearranging its characters and print the final rearranged string too.

If there exist multiple answers, print the lexicographically largest string possible.

Note:

K – Magical String solution codechef

  • Each query will be treated independently i.e. after each query the string will remain the same as it was initially.
  • The input files are large. The use of Fast I/O is recommended.

Input Format

K – Magical String solution codechef

  • The first line contains TT denoting the number of test cases.
  • The first line of each test case contains an integer NN denoting the length of the string.
  • The second line of each test case contains the string SS given in question.
  • The third line of the test case contains an integer QQ denoting the number of queries.
  • Next, QQ lines contain three space-separated integers L,R,L,R, and KK.

Output Format

For each query in each test case, print "Yes" if it is possible to rearrange the characters of that substring such that it can be converted into KK-Magical string and print the rearranged string else print "No" without quotes.

You may print each character of the string in uppercase or lowercase (for example, the strings “yEs”, “yes”, “Yes” and “YES” will all be treated as identical).

Constraints

K – Magical String solution codechef

  • 1T1001≤T≤100
  • 1N1051≤N≤105
  • 1Q1051≤Q≤105
  • 1LRN1≤L≤R≤N
  • 1KN1≤K≤N
  • The sum of (RL+1)(R−L+1) over all QQ queries over all test cases whose answer is "Yes" is less than or equal to 106106.

Sample Input 1

K – Magical String solution codechef

1
9
EFDAABCBD
4
1 9 6
6 8 1
4 7 3
1 2 1

Sample Output 1

K – Magical String solution codechef

Yes
FEDAABBCD
No
Yes
CAAB
Yes
FE

Explanation

K – Magical String solution codechef

Test case 11:

For the first query : L=1,R=9,K=6L=1,R=9,K=6 , the substring we are concerned with is "EFDAABCBD", we can rearrange its characters to "FEDAABBCD". Now, as it has the longest non-decreasing subsequence of size exactly K=6K=6 (The longest non decreasing subsequence being "AABBCD"). Therefore, the answer to this query is “Yes”.

For the second query: L=6,R=8,K=1L=6,R=8,K=1, the substring is "BCB", as there is no way in which we could rearrange the characters such that the longest non decreasing subsequence could become of size exactly K=1K=1. Therefore, the answer to this query is “No”.

For the third query: L=4,R=7,K=3L=4,R=7,K=3 , the substring is "AABC", we can rearrange its characters to "CAAB". Now, as this string has the longest non-decreasing subsequence of size exactly K=3K=3 and the subsequence will be "AAB". Therefore the answer to this query is “Yes”.

For the fourth query: L=1,R=2,K=1L=1,R=2,K=1, the substring is "EF", we can rearrange its characters to "FE" . Now, as this string has the longest non-decreasing subsequence of size exactly K=1K=1 and the subsequence will be "F". Therefore the answer to this query is “Yes”.

Leave a Comment