思路: 数学优化 + 哈希表
暴力思路：对于一个位置i，我们考虑往前找所有s[i] == s[j] 的位置j。那么[j+1,i-1]这一段的任意一个字符都可以被选择，也就是j对i的答案贡献就是j - i - 1。也就是找到所有的j，去求和。
那么位置i的答案是:
发现第一个求和式的内容(i - 1) 与 j无关:
题目内容
魔法学院对字符串进行研究时，发明了一种衡量字符串「魔法值」的方法。对于一个仅由小写字母组成的字符串，它的魔法值定义为：选取三个位置 i<j<k，且满足 s[i]=s[k] 的三元组 (i,j,k) 的个数。换言之，魔法值就是首尾字符相同的长度为 3 的子序列的数量。
现在给定一个长度为 n 的字符串，请你对每个前缀计算魔法值。
约束条件：字符串长度 n 满足 1≤n≤105，字符串中仅包含小写字母。
输入描述
