103292: [Atcoder]ABC329 C - Count xxx

Problem Statement

You are given a string $S$ of length $N$ consisting of lowercase English letters.

Find the number of non-empty substrings of $S$ that are repetitions of one character. Here, two substrings that are equal as strings are not distinguished even if they are obtained differently.

A non-empty substring of $S$ is a string of length at least one obtained by deleting zero or more characters from the beginning and zero or more characters from the end of $S$. For example, ab and abc are non-empty substrings of abc, while ac and the empty string are not.

Constraints

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

Input

The input is given from Standard Input in the following format:

$N$
$S$

Output

Print the number of non-empty substrings of $S$ that are repetitions of one character.

Sample Input 1

6
aaabaa

Sample Output 1

4

The non-empty substrings of $S$ that are repetitions of one character are a, aa, aaa, and b; there are four of them. Note that there are multiple ways to obtain a or aa from $S$, but each should only be counted once.

Sample Input 2

1
x

Sample Output 2

1

Sample Input 3

12
ssskkyskkkky

Sample Output 3

8

问题描述

你有一个长度为 N 的由小写英文字母组成的字符串 S。

找出 S 中的非空子串个数，这些子串都是由一个字符重复组成的。这里的两个子串，即使通过不同的方式得到，如果它们作为字符串是相等的，则被视为相同的子串。

S 的一个非空子串是指从 S 的开头删除零个或多个字符，再从 S 的结尾删除零个或多个字符得到的长度至少为一的字符串。例如，ab 和 abc 是 abc 的非空子串，而 ac 和空字符串则不是。

约束条件

• $1 \leq N \leq 2\times 10^5$
• $S$ 是一个长度为 N 的由小写英文字母组成的字符串。

输入

输入数据从标准输入中给出，格式如下：

$N$
$S$

输出

输出 S 中的非空子串个数，这些子串都是由一个字符重复组成的。

样例输入 1

6
aaabaa

样例输出 1

4

S 的非空子串中，由一个字符重复组成的有 a、aa、aaa 和 b，共四个。注意，即使有多种方法从 S 中得到 a 或 aa，但每个应该只计算一次。

样例输入 2

1
x

样例输出 2

1

样例输入 3

12
ssskkyskkkky

样例输出 3

8