Reorganized String


  • 0

    Click here to see the full article post


  • 0
    J

    Good analysis, smart approach. Thanks for sharing.


  • 0
    Y

    @awaice for python solution, why need this judgement:

    if not ans or ch1 != ans[-1]:
    

    if ch1==ans[-1] happens, since ch1 and ch2 were already poped and will never be pushed back, the result will not be valid since some chars missing.
    also "any(-nc > (len(S) + 1) / 2 for nc, x in pq)" has already excluded the invalid case, so will ch1==ans[-1] happen?


  • 0

    @ywh1988 The solution has been corrected, thanks.


  • 0
    M

    if (ans.length() == 0 || mc1.letter != ans.charAt(ans.length() - 1))
    Do we need this condition in approach 2?
    In the current code, if happen those two characters will be ignored. So, Ans will be incorrect.


  • 0
    S

    Testing Link for Google Google


  • 0
    L

    @awice. The condition "if not ans or ch1 != ans[-1]:" is not necessary.
    suppose in the previous iteration, ['a', 'b'] has been appended to ans. With the condition you are trying to say if in the current iteration, if 'b' has become the MOST common character, don't append it to ans since it will create a sequence of ['a', 'b', 'b'] which is invalid.

    But in the previous iteration, 'a' is the MOST common character. With the counters of 'a' and 'b' both being decremented by 1, the current iteration, there is no way that 'b' will ever become the MOST common character.

    So the condition above will always hold True and is not necessary. I have removed the condition and my answer gets AC too.


  • 0
    M

    Solution #1: why need sort here?
    just Put max freq element in the 0,2,... seprately

    The Time Complexity would be O(N)


Log in to reply
 

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