ICPC PNW 2016

alphabet

A string is alphabetical if deleting 1 or more of its letters results in an alphabet string, a to z (abcdefg....wxyz).

Given a string, determine the minimum number of letters required to make it alphabetical.

Example input: xyzabcdefghijklmnopqrstuvw

Output: 3

Example input: aiemckgobjfndlhp

Output: 20

approach

Start with an empty stack
Push first letter on to stack
For each remaining letter in the string:
    comesbefore = false
    compare this letter to stack.peek(), if it comes before, set comesbefore = true
    while(comesbefore):
        pop the stack
        compare this letter to stack.peek, if it comes before, set comesbefore = true
    push this letter onto the stack
Return 26 - stack.size()

The trick here was just to think this out by hand, one step at a time:

a
ai
aie -> ae
aem
aemc -> aec -> ac

if c < m, pop m
if c < e, pop e