A - Remove One Character 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

長さ N の文字列 S が与えられます。 1\leq i\leq N に対して、S からその i 文字目を削除してできる文字列を S_i と表します。

整数の組 (i,j) であって、次の条件をともに満たすものの個数を求めてください。

  • 1\leq i < j\leq N
  • S_i = S_j

制約

  • 2\leq N\leq 3\times 10^5
  • S は英小文字からなる長さ N の文字列である

入力

入力は以下の形式で標準入力から与えられます。

N
S

出力

答えを出力してください。

入力例 1

7
abbbcca

出力例 1

4

S_i は、順に以下の文字列となります：bbbcca, abbcca, abbcca, abbcca, abbbca, abbbca, abbbcc

条件を満たす (i,j) は以下の 4 個です。

  • (i,j) = (2,3)
  • (i,j) = (2,4)
  • (i,j) = (3,4)
  • (i,j) = (5,6)

入力例 2

4
xxxx

出力例 2

6

入力例 3

2
pp

出力例 3

1

入力例 4

2
st

出力例 4

0

Score : 300 points

Problem Statement

You are given a string S of length N. For each 1\leq i\leq N, let S_i denote the string obtained by deleting the i-th character from S.

Find the number of pairs of integers (i,j) that satisfy both of the conditions below.

  • 1\leq i < j\leq N
  • S_i = S_j

Constraints

  • 2\leq N\leq 3\times 10^5
  • S is a string of length N consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the answer.

Sample Input 1

7
abbbcca

Sample Output 1

4

Here are the strings S_i in order: bbbcca, abbcca, abbcca, abbcca, abbbca, abbbca, abbbcc.

The following 4 pairs (i,j) satisfy the conditions.

  • (i,j) = (2,3)
  • (i,j) = (2,4)
  • (i,j) = (3,4)
  • (i,j) = (5,6)

Sample Input 2

4
xxxx

Sample Output 2

6

Sample Input 3

2
pp

Sample Output 3

1

Sample Input 4

2
st

Sample Output 4

0