LeetCode [358] Rearrange String k Distance Apart

Given a non-empty string s and an integer k, rearrange the string such that the same characters are at least distance k from each other.

All input strings are given in lowercase letters. If it is not possible to rearrange the string, return an empty string "".

Example 1:

Input: s = "aabbcc", k = 3
Output: "abcabc" 
Explanation: The same letters are at least distance 3 from each other.

Example 2:

Input: s = "aaabc", k = 3
Output: "" 
Explanation: It is not possible to rearrange the string.

Example 3:

Input: s = "aaadbbcc", k = 2
Output: "abacabcd"
Explanation: The same letters are at least distance 2 from each other.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

class Solution { public: //find the next valid char can be pus at "index" int getChar(vector<int>& counts, vector<int>& valid, int index) { int m = 0, offset = -1; for(int i=0; i<26; ++i) { if(counts[i]>m && index>=valid[i]) { m = counts[i];//greedy: use the char with max count offset = i; } } return offset; } string rearrangeString(string s, int k) { if(k==0) return s; int n = s.size(); vector<int> counts(26, 0);//counts[i] is count of char('a'+i) vector<int> valid(26, 0);//valid[i] is the next smallest valid position of char('a'+i) for(auto c:s) counts[c-'a']++; string ret; for(int i=0; i<n; ++i) { int offset = getChar(counts, valid, i); if(offset<0) return "";//cannot find a valid char ret += ('a'+offset); counts[offset]--; valid[offset] = i+k; } return ret; } };