My simple O(N) idea

  • 4

    Scan from start to end, then check if

    • s[i]>s[i+1], delete s[i];
    • s[i]<=s[i+1], don't delete s[i] continue;

    If we still need to delete, delete from the end.

    Total: O(N).

    Correctness: we only delete if there is "descending". The reason is, if there is an "ascending", say s[i]<=s[i+1], and we delete s[i], then since s[i+1]>s[i], the result can't be the minimal.

  • 0

    I think you need to to this K pass so it should be O(N * K)?

  • 0

    This idea is the same as my solution
    And it is O(n + k) = O(n) (if you can remove a letter in O(1)) as it only does 1 pass with at most k returns to previous letter.

  • 0

    @dettier Yes, you're right, the point is that we only need to return to previous letter after removing a letter, instead of start from the beginning again. Good solution.

Log in to reply

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