Greedy Solution Beats 95%


  • 12
    O

    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

  • 2
    D

    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).


  • 6
    S

    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.


  • 1
    O

    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


  • 0

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


  • 1

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


  • 0
    H

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


Log in to reply
 

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