103292: [Atcoder]ABC329 C - Count xxx

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:6 Solved:0

Description

Score : $300$ points

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

Output

分数:300分

问题描述

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

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

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

约束条件

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

输入

输入数据从标准输入中给出,格式如下:

$N$
$S$

输出

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


样例输入 1

6
aaabaa

样例输出 1

4

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


样例输入 2

1
x

样例输出 2

1

样例输入 3

12
ssskkyskkkky

样例输出 3

8

HINT

统计长度为n的字符串,有多少种仅包含1种字母的子串?

加入题单

上一题 下一题 算法标签: