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:
Greedy: place most frequent chars first. a at 0,3; b at 1,4; c at 2,5. Each pair is exactly 3 apart.
Input:
s = "aaabc", k = 3Output:
""Explanation:
3 'a's need positions 0,3,6 but string has only 5 chars. Impossible to space 'a's 3 apart; return empty.
Input:
s = "aabbc", k = 2Output:
abacbExplanation:
Frequencies: a:2, b:2, c:1. Place 'abacb': a at 0,2; b at 1,3; c at 4. Each duplicate is 2+ apart.
Constraints
- •
1 ≤ s.length ≤ 3 × 10⁵ - •
s consists of lowercase English letters. - •
0 ≤ k ≤ s.length