Description
Given a string s and an integer k, rearrange s such that the same characters are at least k distance apart. Return the rearranged string, or empty string if not possible.
Examples
Input:
s = "aabbcc", k = 3Output:
"abcabc"Explanation:
Same characters are 3 apart.
Input:
s = "aaabc", k = 3Output:
""Explanation:
Edge case with empty result.
Input:
s = "aabbc", k = 2Output:
abacbExplanation:
Same characters must be at least 2 positions apart. With frequencies a:2, b:2, c:1, one valid arrangement is 'abacb' where each 'a' and each 'b' are exactly 2 positions apart from their duplicates.
Constraints
- •
1 ≤ s.length ≤ 3 × 10⁵ - •
s consists of lowercase English letters. - •
0 ≤ k ≤ s.length