洛谷9348题解
首先，我们知道，有一种最小化\(T\)的通用方法：逐位确定。
这道题可以这么做，然后使用dp判定合法性。
然而这样子没什么前途，需要挖掘这道题的性质。
首先我们会发现：设\(S\)最小的字符为\(x\)，\(S\)有\(k\)个\(x\)，这为\(T\)的前\(k\)个\(x\)可以作为\(T\)的\(k\)位，而这显然是最优解。
因为我们可以不进行3操作，对\(S\)中的非\(x\)字符进行2操作，\(x\)字符进行1操作。
考虑如果我们让\(k\)个\(x\)可以作为\(T\)的\(k\)位我们需要对串进行什么操作。可以发现执行\(3\)操作会操作\(S\)的一段后缀，\(1,2\)操作会操作\(S\)的一段前缀，枚举进行\(3\)操作后缀长度\(l\)。\(s_{l...n}\)一定最多包含一个\(x\)，否则因为\(s_{l...n}\)进行3操作成为\(S\)的一个子序列，肯定存在一个非\(x\)字符排在\(x\)前面。而且为了满足上面的条件，我们需要在\(S\)操作到\(x\)成为字符的首位时（即进行\(1,2\)前缀操作到第一个\(x\)时，此时肯定进行\(1\)操作），让\(S\)的第\(1\)个\(x\)的位置（设为\(p\)）\(~l-1\)的所有非\(x\)字符（\(x\)字符进行\(1\)操作 ）都要进行2操作放在\(S\)的末尾。
\(s_{1...p-1}\)可以任意进行操作。最后的\(T\)为