UTPC の連続する部分文字列（UTP や TP, C など）のことを、以下では塊と呼ぶことにします。

U, T, P, C の \(4\) 文字は辞書順と逆順に並んでいる、ということに着目します。このことから、次の性質が成り立ちます（証明は容易なので省略します）。

• 連続する部分文字列 UTPC を作る過程で、U, T, P, C の各文字の相対的な位置が入れ替わる、ということはない。

これにより、連続する部分文字列として UTPC を作るには、ある塊に対して別の文字をつなげることによって、塊を大きくしていくことによって生成することになります。また、先ほどの「U, T, P, C の \(4\) 文字は辞書順と逆順に並んでいる」により、次の性質も成り立ちます。

• \(1\) 回の操作で、塊の大きさを \(2\) 以上大きくすることはできない。

したがって、操作を行うことで、塊の大きさを高々 \(1\) ずつ大きくしていくことになります。以下、どの塊から開始するかを固定して考えることにします。

このとき、考えるべき塊のパターンは、次の \(10\) パターンとなります。

1. UTPC
2. UTP
3. TPC
4. UT
5. TP
6. PC
7. U
8. T
9. P
10. C

これらのパターン一つ一つについて、そのパターンの場合に最終的に UTPC を作るのに必要な条件および、その際の回数の最小値を考えていくことにします。

---

1. UTPC から開始する場合

この場合は、はじめから条件を満たしています。そのため、無条件で必要な操作回数は \(0\) 回となります。

2. UTP から開始する場合

P より後ろに C がある場合、P の一つ後ろの文字から C までの区間に対して操作を行うことで、 UTPC を作ることが可能です。よって、以下の条件を満たせば、\(1\) 回の操作で UTPC を作ることが可能です。一方、そうでなければ UTPC を作ることは明らかに不可能です。

• その塊における P より後ろに C が存在する。

3. TPC から開始する場合

上記同様、以下の条件を満たせば、\(1\) 回の操作で UTPC を作ることが可能となり、そうでなければ UTPC を作ることは不可能です。

• その塊における T より前に U が存在する。

4. UT から開始する場合

UT の塊の後ろに P を付け加える場合は、操作を行う区間の左端を T のひとつ後ろにし、なおかつ その区間が P を含む必要があります。ここでは、区間の右端は T より後ろで最初に登場する P としてかまいません。

この区間が C を含まない場合は、その区間に対して操作を行うことによって、UT の後ろに P を付け加えることが可能となり、パターン 2 に帰着できます。一方、C を含む場合は、その区間に操作を行うと、UT の後ろに C が付け加えられてしまうため、UT の後ろに P を付け加えることは不可能となります。

以上の議論により、以下の条件を満たせば、\(2\) 回の操作で UTPC を作ることが可能となり、そうでない場合は UTPC を作ることは不可能です。

• その塊における T より後ろに P が存在し、かつ T と P の間に C が存在しない。
• その P より後ろに、C が存在する。

5. TP から開始する場合

パターン 2 およびパターン 3 の議論により、以下の条件を両方とも満たせば、\(2\) 回の操作で UTPC を作ることが可能となり、そうでなければ UTPC を作ることは不可能です。

• その塊における T より前に U が存在する。
• その塊における P より後ろに C が存在する。

6. PC から開始する場合

パターン 4 と同様の議論により、以下の条件を両方とも満たせば、\(2\) 回の操作で UTPC を作ることが可能となり、そうでなければ UTPC を作ることは不可能です。

• その塊における P より前に T が存在し、かつ T と P の間に U が存在しない。
• その T より前に、U が存在する。

7. U から開始する場合

まず、U に T を付け加えて UT の塊を作る必要がありますが、これは パターン 8 のように、T に U を付け加えることで生成するほうが、より厳しくない条件で可能です。したがって、このパターンを考える必要はありません。

8. T から開始する場合

パターン 3 およびパターン 4 の議論により、以下の \(3\) つの条件を全て満たす場合は \(3\) 回の操作で UTPC を作ることが可能です。

• その塊における T より前に U が存在する。
• その塊における T より後ろに P が存在し、かつ T と P の間に C が存在しない。
• その P より後ろに、C が存在する。

この条件のうち、\(1\) 個目の条件、 \(2\) 個目の条件のうちの「T より後ろの P の存在性」の条件、および \(3\) 個目の条件のいずれか一つでも満たさない場合は、明らかに UTPC を作ることは不可能です。

一方、「T と P の間に C が存在しない。」という条件のみ満たさない場合については、T を左端とし、かつ C を含む区間について操作を行うことにより、「T と P の間に C が存在しない。」という条件も満たす場合に帰着できます。したがって、この場合に UTPC を作るために必要な操作回数は \(4\) 回となります。

9. P から開始する場合

パターン 8 と同様に考えればよいです。以下の \(3\) つの条件を全て満たす場合は \(3\) 回の操作で UTPC を作ることが可能です。

• その塊における P より後ろに C が存在する。
• その塊における P より前に T が存在し、かつ T と P の間に U が存在しない。
• その T より前に、U が存在する。

この条件のうち、\(1\) 個目の条件、 \(2\) 個目の条件のうちの「P より前の T の存在性」の条件、および \(3\) 個目の条件のいずれか一つでも満たさない場合は、明らかに UTPC を作ることは不可能です。一方、「T と P の間に U が存在しない。」という条件のみ満たさない場合は \(4\) 回の操作で UTPC を作ることが可能です。

10. C から開始する場合

パターン 7 同様、このパターンを考える必要はありません。

---

これにより、開始時の塊全ての場合について、必要な操作回数の最小値の判定方法がわかりました。

以上の判定は、「そのインデックスより後ろ（前）にある最も近い U, T, P, C の位置」を \(O(N)\) で前計算により求めておくことにより、最初に考える塊 \(1\) 個あたり \(O(1)\) ですべて可能となります。

これにより、最初の塊として考えられるパターンをすべて試すことで、この問題を解くことができます。これは全体で \(O(N)\) で実行可能であり、十分高速に動作します。