ABC345 C - One Time Swap

atcoder.jp

問題

• 文字列$S$が与えられるよ
• 次の操作を1回行った後の文字列として、有り得るものはいくつある？
  • Sのうち2つの文字を選んで、入れ替える

成約

• $2 \leq |S| \leq 10^{6}$

思考

• $O(N^{2})$は通らない…
• 片方を全探索して、もう片方がサクサクッと求められたら嬉しいね
  • 全探索の典型
  • 手順：
    • 事前準備として、全アルファベットがいくつある？を記録(Counter)
    • 先頭から順に一文字ずつ確認(全探索)
      • Counterから、その1文字分の集計を消す
        • Counterに記録されているのは、「今見ている文字」から右にある文字ごとの数！
      • a~zまでの26文字、順番に数を数えていく
        • 「今見ている文字」と同じ文字の個数に関して取り扱い注意！
• そもそも英小文字＝26種類しかないため、文字を2つどう選んでも、$26\times26$しかない
  • aとbを入れ替えるパターンはいくつ？
  • aとcを入れ替えるパターンはいくつ？
  • …
  • bとcを入れ替えるパターンはいくつ？
• こっちで集計したほうが明らかに速いですね！

コード(解1)

from string import ascii_lowercase
from collections import Counter

S = input()
c = Counter(S)

ans = 0
same = 0
for from_c in S:
    c[from_c] -= 1
    for to_c in ascii_lowercase:
        if from_c != to_c:
            ans += c[to_c]
        elif c[to_c] > 0:
            same += 1

if same:
    ans += 1

print(ans)

コード(解2)

from string import ascii_lowercase
from collections import  Counter

S = input()
c = Counter(S)

ans = 0
same = 0
for a in ascii_lowercase:
    for b in ascii_lowercase:
        if a == b:
            if c[a] > 1:
                same += 1
        else:
            ans += c[a] * c[b]

ans //= 2
if same:
    ans += 1

print(ans)