Problem Brief

Min Num Letters

FULLTIMEOA

See Microsoft online assessment and hiring insights

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.

1Example 1

Input

S = "banana"

Output

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

Limits and guarantees your solution can rely on.

the length of string S is within the range [1..100,000]

string S consists only of lower case letters (a-z)

Draft autosaves locally

public int minNumLetters(String S) {
  // write your code here
}

Input

"banana"

Output