思路解析

题目要求：对每个前缀，统计所有子串中首字母和尾字母不相等的个数。

关键点：

1. 子串总数：长度为 i 的前缀一共有 i*(i+1)/2 个子串。

2. 包裹字符串数量：子串首尾相等，来源于相同字母的出现位置。

   • 如果某个字母在前缀中出现了 f 次，那么它能构成的“包裹子串”数量是 f*(f+1)/2。

题目内容

这天，小红薯在小红书上看到了一道每日一题之编程题，如下:

[引用开始]

定义一个字符串是包裹字符串为:字符串的首字母等于最后一个字母。

求解一个字符串的全部子串中，有多少个不是包裹字符串。

[引用结束]

刚好，这两天小红薯正在学习字符串相关的知识，字符串的使用非常广泛，所以要认真的学习。

小红薯在评论区看到了这个问题的进阶版:对于给定的字符串$s_1,s_2..s_n$,对于每一个前缀$[1]$依次求解，它的全部非空子串$[2]$中有多少个不是包裹字符串。

小红薯觉得这个题目很有趣，所以她决定写一个程序，来解决这个问题。

[名词解释]

前缀$[1]$:从原字符串的第一个字符开始，连续选择若干个字符得到的新字符串。一个长度为$n$的字符串有$n$个不同的前缀。

子串$[2]$:从原字符串中，连续的选择一段字符(可以全选)得到的新字符串。

输入描述

第一行输入一个整数$n(1≤n≤2×10^5)$表示字符串长度。

第二行输入一个长度为$n$，由小写字母组成的字符串$s$。

输出描述

一共$n$行，第$i$行输出一个整数，表示原字符串的前缀子串$[1,i]$的全部子串中，不为包裹字符串的数量。

样例1

输入

4
abda

输出

0
1
3
5

说明

对于前缀子串$[1,3]$即"$abd$"，它的全部子串为"$a$"，"$b$"，"$d$"，"$ab$"，"$bd$","$abd$"，前三个是包裹字符串,后三个不是。