CF1383A String Transformation 1 题解

若某一位 \(i\) 上 \(A_i>B_i\)，则显然无解。

否则，建立并查集，然后遍历字符串，若 \(A_i,B_i\) 不在一个集合就合并 \(A_i\) 与 \(B_i\)，直到只剩下一个集合，此时的合并总次数即为答案。

为什么呢？因为将 \(A_i,B_i\) 合并的操作可以视为等价于将以 \(A_i\) 开头的连续若干个相同字符均改为 \(B_i\)，正好就是题目中的所述的操作。

于是当两个字符串中的所有字符都处在同一集合时，\(A=B\)，那么合并次数就是操作次数了。

时间复杂度 \(O(\alpha(n))\)。