Rearranging Characters with Minimum Distance

You are given a string s and an integer k. Your task is to determine whether it is possible to rearrange the characters in s such that any two identical characters are at least k positions apart.

Formally, for every pair of identical characters in the rearranged string, if their positions are i and j (with i < j), then it must hold that:

\(j - i \ge k\)

If such an arrangement exists, print YES; otherwise, print NO.

Hint: A greedy approach using a max-heap (priority queue) along with a waiting queue (to simulate a cooldown of k steps) works well for this problem.

inputFormat

The first line contains an integer T, the number of test cases. Each of the following T lines contains an integer k and a string s separated by a space.

outputFormat

For each test case, output a single line containing either YES or NO indicating whether it is possible to rearrange s so that no two identical characters are within k positions of each other.## sample

7
2 aabbcc
3 aaabc
1 a
1 aa
2 aa
2 abac
2 aaab

YES
NO
YES
YES
NO
YES
NO