Description
Solutions
Min Num Letters
🔥 FULLTIME

Given a word, calculate the smallest number of letters that must be removed in order for the letters of the remaining word to be sorted in lexicographical order. The resulting word need not appear in the dictionary of any particular language.

Given string S, returns the min num of letters that must be removed.

Example 1: 

Input:  S = "banana"
Output: 3 
Explanation:

Because we can remove three letters (the 1st, 3rd and 6th) to get the word "aan", which is sorted. Pls note that it is not possible to remove fewer than 3 letters
Constraints:
  • the length of string S is within the range [1..100,000]
  • string S consists only of lower case letters (a-z)
Thumbnail 0
Testcase
Result
Case 1

input:

output: