101
0/320
Loading content...
You are given a string s consisting of lowercase English letters and an integer k representing the minimum required separation distance. Your task is to reorganize the characters in the string such that any two identical characters are positioned at least k indices apart from each other in the resulting string.
If such a rearrangement is achievable, return any valid rearranged string that satisfies the spacing constraint. If it is impossible to rearrange the characters to meet the requirement, return an empty string "".
The key challenge lies in distributing characters optimally to ensure the spacing requirement is met while using all characters from the original string. When multiple valid rearrangements exist, you may return any one of them.
Understanding the Distance Requirement:
k = 3, if the character 'a' appears at index 0, the next 'a' can appear at index 3 or later (indices 1 and 2 are forbidden for 'a').k = 0 or k = 1, any arrangement is valid since there's no effective spacing constraint.s = "aabbcc"
k = 3"abcabc"Each character appears twice. With k = 3, we need identical characters to be at least 3 positions apart. In "abcabc": the two 'a's are at indices 0 and 3 (distance = 3), the two 'b's are at indices 1 and 4 (distance = 3), and the two 'c's are at indices 2 and 5 (distance = 3). All spacing requirements are satisfied.
s = "aaabc"
k = 3""The character 'a' appears 3 times. With a string length of 5 and k = 3, we would need positions like 0, 3, 6 for the three 'a's, but position 6 exceeds the string bounds. Alternatively, positions 0, 3 and any valid third position cannot satisfy k = 3 spacing. Therefore, no valid arrangement exists, and we return an empty string.
s = "aaadbbcc"
k = 2"abacabcd"With k = 2, identical characters must be at least 2 positions apart. In "abacabcd": 'a' appears at indices 0, 2, 4 (all pairs have distance ≥ 2), 'b' at indices 1, 5 (distance = 4), 'c' at indices 3, 6 (distance = 3), and 'd' at index 7. All spacing constraints are met.
Constraints