concise Java Solution O(N) time O(26) space


  • 78
    F
    // (c[25] - 1) * (n + 1) + 25 - i  is frame size
    // when inserting chars, the frame might be "burst", then tasks.length takes precedence
    // when 25 - i > n, the frame is already full at construction, the following is still valid.
    public class Solution {
        public int leastInterval(char[] tasks, int n) {
    
            int[] c = new int[26];
            for(char t : tasks){
                c[t - 'A']++;
            }
            Arrays.sort(c);
            int i = 25;
            while(i >= 0 && c[i] == c[25]) i--;
    
            return Math.max(tasks.length, (c[25] - 1) * (n + 1) + 25 - i);
        }
    }
    

    First consider the most frequent characters, we can determine their relative positions first and use them as a frame to insert the remaining less frequent characters. Here is a proof by construction:

    Let F be the set of most frequent chars with frequency k.
    We can create k chunks, each chunk is identical and is a string consists of chars in F in a specific fixed order.
    Let the heads of these chunks to be H_i; then H_2 should be at least n chars away from H_1, and so on so forth; then we insert the less frequent chars into the gaps between these chunks sequentially one by one ordered by frequency in a decreasing order and try to fill the k-1 gaps as full or evenly as possible each time you insert a character. In summary, append the less frequent characters to the end of each chunk of the first k-1 chunks sequentially and round and round, then join the chunks and keep their heads' relative distance from each other to be at least n.

    Examples:

    AAAABBBEEFFGG 3

    here X represents a space gap:

    Frame: "AXXXAXXXAXXXA"
    insert 'B': "ABXXABXXABXXA" <--- 'B' has higher frequency than the other characters, insert it first.
    insert 'E': "ABEXABEXABXXA"
    insert 'F': "ABEFABEXABFXA" <--- each time try to fill the k-1 gaps as full or evenly as possible.
    insert 'G': "ABEFABEGABFGA"
    

    AACCCBEEE 2

    3 identical chunks "CE", "CE CE CE" <-- this is a frame
    insert 'A' among the gaps of chunks since it has higher frequency than 'B' ---> "CEACEACE"
    insert 'B' ---> "CEABCEACE" <----- result is tasks.length;
    

    AACCCDDEEE 3

    3 identical chunks "CE", "CE CE CE" <--- this is a frame.
    Begin to insert 'A'->"CEA CEA CE"
    Begin to insert 'B'->"CEABCEABCE" <---- result is tasks.length;
    

    ACCCEEE 2

    3 identical chunks "CE", "CE CE CE" <-- this is a frame
    Begin to insert 'A' --> "CEACE CE" <-- result is (c[25] - 1) * (n + 1) + 25 -i = 2 * 3 + 2 = 8

  • 4
    W

    You are so smart!!


  • 2

    Cool! Could you explain the last line? Thanks!


  • 0
    F
    This post is deleted!

  • 14

    @BryanBo.Cao
    for the last line (c[25] - 1) * (n + 1) + 25 - i):

    c[25]-1: the most frequent letter happen time minus 1
    *(n+1): count for the loops for above
    +25-i: count for the less frequence letters.
    

    For example:
    tasks = ['A','A','A','B','B','B'], n = 2

    most frequent letter : A (happen 3 times, let it minus 1= 2)
    count loops: (n+1) =3
    plus the letters left: A,B.
    [A -> B -> idle]*loop1* -> [A -> B -> idle]*loop2* -> A -> B.
    

    sorry for this kind of not clear explanation.


  • 0
    F
    This post is deleted!

  • 0
    A
    This post is deleted!

  • 2
    G

    Can you describe the process of AAAABBBEEFFGG when n is 3,
    I get the string 'ABEF ABEF ABG_ A_G',the result is 14,but it's not correct. there may be not a specific process but a strict proof.


  • 0
    W

    @Gobella1 said in concise Java Solution O(N) time O(26) space:

    AAAABBBEEFFGG

    ABEF ABGE ABFG A, result 13 is right


  • 4
    F

    @Gobella1

    You have to try to fill the k - 1 gaps full, then go around to the first gap. See 'F' below.

    AAAABBBEEFFGG

    here X represents a space gap:

    Frame: "AXXXAXXXAXXXA"
    insert 'B': "ABXXABXXABXXA" <--- 'B' has higher frequency than the other characters, insert it first.
    insert 'E': ABEXABEXABXXA"
    insert 'F': "ABEFABEXABFXA" <--- each time try to fill the k-1 gaps as full as possible.
    insert 'G': "ABEFABEGABFGA"


  • 5

    I think the prove here is not very rigorous although it is correct. For example if the task are AAABBCC, n = 1, you can not fill it in the way you described ABABA, because it then requires ABABAC C, total of 8 while it actually just need 7 in the form of ABACABC etc. Could you give a rigorous prove why in that case task.length will be the answer? Thanks.


  • 3

  • 1
    F

    @dreamchase

    Read 2nd example, or the phrase "append to the end of each chunk of the first k-1 chunks sequentially and round and round, then join the chunks" might be more appropriate.


  • 1

    @fatalme Ok, that makes more sense. In another word, the frame is not rigid but rather "stretchable"


  • 1
    M

    Thanks very much for sharing, this is a truly smart approach


  • 17
    M

    @dwyanecf Thanks for the explain, please let me give a try, using the terms in the solution:
    for the last line (c[25] - 1) * (n + 1) + 25 - i:

    c[25]-1: we have totally "c[25]" frames,
    *(n+1): the length of each frame, each of the first c[25]-1 frames must have a length of "n+1"
    +25-i: count for the most frequent letters, it is the length of the last frame


  • 0
    D

    @dreamchase because A can regarded task B and task C is the same task, So there is no difference ABAC or ABAB, you can put B or C beside A, but how to prove you can see the simulation way, this maybe can help you understand why is task.length. Every time we choose the most frequceny task to put the next position, So if B = 2 C = 2, when reduce the frequency of B, it became 1 so the next time we will choose C not B.


  • 0
    D
    This post is deleted!

  • 3
    D

    due to Arrays.sort, this solutions time complexity should be O(NLongN).


  • 12
    N

    @darren5 Length of array is fixed 26, so even use sort, so O(26*log(26)) is still constant time


Log in to reply
 

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