How do you come up with the greedy strategy?


  • 0
    Z

    The sequence of N keystrokes which produces an optimal string length will start with m As and end with a suffix of Ctrl-A, a Ctrl-C, followed by only Ctrl-V's

    How do you figure this out? It is more intuitive to come up with a search + memo.


  • 0
    S

    You sure your conclusion is right? For N = 11, the optimal sequence is AAA, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V. Select and copy appear twice.

    If you mean a single A won't ever appear after a copy-paste, this is apparent since you always would move this single A before the copy-paste so that you gain at least one more A.


  • 0
    Z

    @Spin0za
    your optimal sequence is following this "a suffix of Ctrl-A, a Ctrl-C, followed by only Ctrl-V's" pattern, whatever come before doesn't matter. My question is how/why this is right and how to figure it out. Let me know if it makes sense to you.


  • 0
    S

    @zshen9 I explained to you in my 2nd paragraph. Once you copy-paste, you won't want to type a single A anymore, you'd rather do it earlier. This is an exchange argument.


  • 0
    Z

    @Spin0za
    yes, thanks for your explanation.


Log in to reply
 

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