#K4676. K-Distance Character Reordering
K-Distance Character Reordering
K-Distance Character Reordering
Given a string S consisting of lowercase letters and an integer K, determine whether it is possible to rearrange the characters of S such that no two adjacent characters are the same and for any two identical characters, the difference between their positions is at least \(K\). In other words, if the positions of any two identical characters are \(i\) and \(j\) with \(i < j\), then it must hold that \(j - i \ge K\).
This problem is a variation of the classic "Rearrange String k Distance Apart" challenge. You are required to process multiple test cases. For each test case, output "Possible" if the required rearrangement exists, or "Impossible" otherwise.
inputFormat
The input begins with a single integer T (1 ≤ T ≤ 100) denoting the number of test cases. Each test case is given on a separate line containing a string S (1 ≤ |S| ≤ 105, consisting of lowercase letters) and an integer K (K ≥ 1) separated by a space.
Example:
3 aabbcc 2 aa 2 abcabc 3
outputFormat
For each test case, print a single line with either "Possible" or "Impossible" depending on whether it is possible to rearrange the string such that no two adjacent identical characters exist and all identical characters are at least \(K\) positions apart.
Example:
Possible Impossible Possible## sample
3
aabbcc 2
aa 2
abcabc 3
Possible
Impossible
Possible