ある文字列に対して、その部分列ではない文字列のなかで一番短く、さらに辞書順最小のものを求める。
これはDPで求めることができて、DPテーブルは $$DP[i]={\rm 前から}i{\rm 文字目以降の文字列の部分列ではない文字列の最小文字数}$$ となる。
はじめに最小非部分列の長さを求める。ある文字列の最小非部分列が'a'から始まるとすると、それは「'a'+"はじめに出てくる'a'の次の文字以降の最小非部分列"」になる。'b','c',...にも同じことがいえて、それらのうちで一番短いものが最短である（各場所について、それ以降で各文字が出てくる最初の位置を求めておく）。よって、DPテーブルの遷移は $$DP[i]={\rm min\{各文字が最初に出てくる場所の次の文字以降の最小非部分列+1\}}$$ となる（後ろからやる必要がある）。
最小非部分列の長さがわかったら、具体的に辞書順最小のものを構築する。これは、0文字目から、次に各文字が出てくる場所を見て、DP[i]が一番小さい文字のなかで辞書順最小の文字がある場所に飛ぶことを繰り返せばよい。