> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/greedy/358.-rearrange-string-k-distance-apart.md).

# 358. Rearrange String k Distance Apart

对给定字符串重排序，使得两个相同字符之间至少间隔k。靠直觉贪心做，对i从能放在i的可选字符中选剩下数目最多放入。如果不是选数目最多的放入最后它们剩下来就凑不足其它元素来间隔开它们。比如aaabbc, k = 1; 不先选掉a的话会成为bcbaaa, 但其实可以组成ababac。

```cpp
class Solution {
public:
    string rearrangeString(string str, int k) {
        vector<int> count(26), valid(26);
        for (const auto c : str) {
            ++count[c - 'a'];
        }
        const auto next = [&](int index) {
            int mx = 0, res = -1;
            for (int i = 0; i < 26; ++i) {
                if (count[i] > mx && valid[i] <= index) {
                    res = i;
                    mx = count[i];
                }
            }
            return (char) (res + 'a'); 
        };
        string res;
        for (int i = 0; i < str.length(); ++i) {
            auto nc = next(i);
            res += nc;
            --count[nc - 'a'];
            valid[nc - 'a'] += i + k - 1;
        }
        return res;
    }
};

```