## Rearrange String k Distance Apart

• Time:O(26n) = O(n)
• Space:O(128) = O(1)

## C++

``````class Solution {
public:
string rearrangeString(string s, int k) {
const int n = s.length();
string ans;
vector<int> count(128);
vector<int> valid(128);  // valid[i] := the leftmost index char i can appear

for (const char c : s)
++count[c];

for (int i = 0; i < n; ++i) {
const char c = getBestLetter(count, valid, i);
if (c == '*')
return "";
ans += c;
--count[c];
valid[c] = i + k;
}

return ans;
}

// return the letter that has most count and also valid
private:
char getBestLetter(const vector<int>& count, const vector<int>& valid,
int index) {
int maxCount = -1;
char bestLetter = '*';

for (char c = 'a'; c <= 'z'; ++c)
if (count[c] > 0 && count[c] > maxCount && index >= valid[c]) {
bestLetter = c;
maxCount = count[c];
}

return bestLetter;
}
};
``````

## JAVA

``````class Solution {
public String rearrangeString(String s, int k) {
final int n = s.length();
StringBuilder sb = new StringBuilder();
int[] count = new int[128];
int[] valid = new int[128]; // valid[i] := the leftmost index char i can appear

for (final char c : s.toCharArray())
++count[c];

for (int i = 0; i < n; ++i) {
final char c = getBestLetter(count, valid, i);
if (c == '*')
return "";
sb.append(c);
--count[c];
valid[c] = i + k;
}

return sb.toString();
}

// return the letter that has most count and also valid
private char getBestLetter(int[] count, int[] valid, int index) {
int maxCount = -1;
char bestLetter = '*';

for (char c = 'a'; c <= 'z'; ++c)
if (count[c] > 0 && count[c] > maxCount && index >= valid[c]) {
bestLetter = c;
maxCount = count[c];
}

return bestLetter;
}
}
``````

## Python

``````class Solution:
def rearrangeString(self, s: str, k: int) -> str:
n = len(s)
ans = []
count = Counter(s)
valid = Counter()  # valid[i] := the leftmost index i can appear

# return the letter that has most count and also valid
def getBestLetter(index: int) -> chr:
maxCount = -1
bestLetter = '*'

for c in string.ascii_lowercase:
if count[c] > 0 and count[c] > maxCount and index >= valid[c]:
bestLetter = c
maxCount = count[c]

return bestLetter

for i in range(n):
c = getBestLetter(i)
if c == '*':
return ''
ans.append(c)
count[c] -= 1
valid[c] = i + k

return ''.join(ans)
``````