Min Num Letters

A Microsoft interviews coding interview problem: Given a lowercase string S (length 1–100,000), determine the minimum number of letters to remove so the remaining characters are in lexicographical order. This interview question focuses on string properties and ordering; the resulting word need not be a real dictionary word.