# Greedy Solution Beats 95%

• The idea is:

for example: "aaabbcc", k = 3

1. Count the statistics of letters, sort them in terms of frequency in a descending way.

so it has the result: a - 3, b - 2, c - 2.

1. Suppose the rewrite string length is len, divide the len into bins of size k, so in total
you have

bin number of nBin = (len - 1) / k + 1,

with last bin size:

lastBinSize = len % k.

in the example, nBin = 3, lastBinSize = 1;

1. Fill the same letter in different bins:

after filling 'a' ---> result = a##a##a

after filling 'b' ---> result = ab#ab#a

after filling 'c' ---> result = abcabca

Below is the implementation code:

``````public class Solution {
private final static int sizeAZ = 26;
public String rearrangeString(String str, int k) {
if (k <= 1) return str;
char[] c = str.toCharArray();
int[][] cnt = new int[sizeAZ][2];
int len = c.length;
for (int i = 0; i < sizeAZ; cnt[i][0] = i++); // save letter id
for (int i = 0; i < len; c[i++] = '*')
cnt[c[i] - 'a'][1]++;

// Sort according to occurance frequency, descending
Arrays.sort(cnt, new Comparator<int[]>(){
@Override
public int compare(int[] a, int[] b) {
return b[1] - a[1];
}
});

int nBin = (len - 1) / k + 1, sizeLastBin = len % k;
int[] idx = new int[nBin];
//System.out.println(nBin + ",,," + sizeLastBin);
for (int u = 0, i = 0; u < sizeAZ; u++) if (cnt[u][1] > 0) {
char ch = (char)(cnt[u][0] + 'a');
int m = cnt[u][1];
if (m > nBin) return ""; // Bins are not enough for ch, for sure
for (int y = 0; y < m; y++) {
while (idx[i] >= binSize(i, k, len))
i = (i + 1) % nBin;

int offset = i * k;
if (idx[i] > 0 && c[offset + idx[i] - 1] == ch)
return ""; //same letter falls in same bin
c[offset + idx[i]++] = ch;
i = (i + 1) % nBin;
}
}
return new String(c);
}

private int binSize(int i, int k, int len) {
return Math.min(len - i * k, k);
}
} //14ms``````

• I think this is a great solution. More importantly, this solution gives the proof of why greedy method is correct. The greedy method says: if there exists a solution, the greedy method can find it (by always choosing the most frequent character first). The proof is: after choosing the most frequent character A, and fill these As into buckets, we can guarantee that their distance is >=k. However, if you don't choose greedy method, and choose some less frequent character B first, and fill Bs into buckets. Then you choose A, there is a chance that As might not have >=k distance apart (because #A > #B).

• This code does not work for "abcdabcdabdeac", k = 4
Suppose there are n bins, one character is filled into the bins in the order m+1,...., n, 0, ..., m
The two characters filled into the bin m+1 and m have distance less than k, like the last two "d" in this example.

• Yeah you are correct, I think Leetcode should add this test case to show the edge case that is not considered by this greedy algorithm

• @sangyezi @1337c0d3r I agree with this comment. May need to add additional test case.

• Thanks, this is a great test case. I have just added @sangyezi 's test case.

• @sangyezi
a---a---a---a-
ab--ab--ab--a-
abc-abc-abc-a-
abcdabcdabcda-
abcdabcdabcdae

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.