Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 350 点
問題文
文字列 S が与えられます。次の操作を ちょうど 1 回 行った後の文字列としてあり得るものがいくつあるか求めてください。
- S の長さを N とする。 1\leq i<j\leq N をみたす整数の組 (i,j) を選び、S の i 文字目と j 文字目を入れ替える。
なお、この問題の制約下で操作を必ず行うことができることが証明できます。
制約
- S は英小文字からなる長さ 2 以上 10^6 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S に対して問題文中の操作をちょうど 1 回行った後の文字列としてあり得るものの個数を出力せよ。
入力例 1
abc
出力例 1
3
S の長さは 3 であるため、1\leq i<j\leq 3 をみたす整数の組 (i,j) としては、 (1,2), (1,3), (2,3) の 3 通りが考えられます。
- S の 1 文字目と 2 文字目を入れ替えた時、S は
bac
となります。 - S の 1 文字目と 3 文字目を入れ替えた時、S は
cba
となります。 - S の 2 文字目と 3 文字目を入れ替えた時、S は
acb
となります。
よって、abc
に対して操作を行った後の文字列としては、bac
, cba
, acb
の 3 つがあり得るため、3 を出力します。
入力例 2
aaaaa
出力例 2
1
どの 2 つの文字を入れ替えても S は aaaaa
のままです。よって、操作後の文字列としてあり得るものは 1 つです。
Points: 350 points
Problem Statement
You are given a string S. Find the number of strings that can result from performing the following operation exactly once.
- Let N be the length of S. Choose a pair of integers (i,j) such that 1\leq i<j\leq N and swap the i-th and j-th characters of S.
It can be proved that you can always perform it under the constraints of this problem.
Constraints
- S is a string of length between 2 and 10^6, inclusive, consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
S
Output
Print the number of strings that can result from performing the operation in the problem statement exactly once on S.
Sample Input 1
abc
Sample Output 1
3
The length of S is 3, so 1\leq i<j\leq 3 is satisfied by three pairs of integers (i,j): (1,2), (1,3), and (2,3).
- Swapping the 1-st and 2-nd characters of S results in S being
bac
. - Swapping the 1-st and 3-rd characters of S results in S being
cba
. - Swapping the 2-nd and 3-rd characters of S results in S being
acb
.
Therefore, the operation on abc
results in one of the three strings: bac
, cba
, and acb
, so print 3.
Sample Input 2
aaaaa
Sample Output 2
1
Swapping any two characters results in S remaining aaaaa
. Thus, only one string can result from the operation.