Maximum Substring

$1$ 文字目が "a" の文字列より、$1$ 文字目が "b" の文字列の方が辞書順で大きく、これは $2$ 文字目以降でも同様です。

ここで、$S$ の $i$ 文字目、すなわち $S_i$ を部分文字列として採用するかを考えます。

$i+1$ 文字目以降に $S_i$ よりも辞書順で遅い文字がある場合は、上の条件から採用しないべきなのは明らかです。$\\$ 逆に、$i+1$ 文字目以降に $S_i$ よりも早い文字しかない場合、つまり $i+1$ 以降で最も遅い文字が $S_i$ より早いときは、$S_i$ を採用したほうが良いです。$\\$ $i+1$ 文字目以降で最も遅い文字が $S_i$ と同じ場合、"a" よりも "aa" の方が辞書順で遅いことを考えると、採用するべきだとわかります。

上記の操作を貪欲に行うことで求める文字列を得られます。