A textile conservator is restoring a long strip of dyed threads. The strip has n threads laid end to end, numbered 0 to n-1, and thread i is dyed with a lowercase color code s[i] (one of 'a' to 'z'). The conservator receives q restoration requests, one at a time. Each request names a contiguous section of the strip by its endpoints l and r (0-indexed, inclusive) and gives a redye budget k. For that request, the conservator may:
Determine whether, using these two operations together, the section can be made to read identically from left to right and from right to left (i.e., form a palindrome). Answer every request independently — the strip itself is never actually modified between requests, so later requests see the original colors.
Line 1: two integers n and q. Line 2: a string s of length n consisting of lowercase English letters. Each of the next q lines contains three integers l, r, k describing one request.
Print q lines. For the i-th request, print YES if the section can be made into a palindrome as described, otherwise print NO.
Example 1
Input
5 2 abcba 0 4 0 0 2 0
Expected
YES NO
Explanation
The full section "abcba" already reads the same forwards and backwards (a:2, b:2, c:1 -> only one letter has an odd count), so it needs 0 redyes: YES. The section "abc" (indices 0..2) has three letters each appearing once (3 odd counts), needing floor(3/2)=1 redye at minimum, but the budget is k=0, so it is not enough: NO.
Example 2
Input
5 2 abcde 0 4 2 0 4 1
Expected
YES NO
Explanation
The whole string "abcde" has all five letters appearing exactly once, so all five counts are odd. Pairing up odd letters two at a time (one redye fixes two of them, leaving at most one as the palindrome's center) needs floor(5/2)=2 redyes at minimum. With budget k=2 that is exactly enough: YES. With budget k=1 it falls one short: NO.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →