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.
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.
This idea is the same as my solution https://discuss.leetcode.com/topic/59327/o-n-solution/2
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.
@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.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.