题解 | abb 后缀和

import sys
"""
 解题 思路 
 https://blog.nowcoder.net/n/3bd0863ecee6487185d6b8217cc01caa
 后缀和数据
 suffix[i+1][j] 表示str 中字母i 位置后面对应的字母a-z出现次数
 从i  后面选择与i位置 不同字母  的两个相同字母j个数cnt  , C（ 2,cnt）=  cnt*(cnt-1)//2
 所以统计 [i+1][0:26]       C（ 2,cnt）=  cnt*(cnt-1)//2  总和
"""

def  sovle():
    n =int(input())
    s=input()
    sum=[ [ 0 for _ in range(26) ] for _  in range(n+1)  ]  # for _  in range(n)
    #逆序统计i位置后面的字母个数
    for i in range(n-1,-1,-1):
        # 复制 i=1 的26个结果到i位置
        #if i< n-1: 
        for  j in range(0,26):
            sum[i][j]=sum[i+1][j]
        
        sum[i][ ord(s[i])-ord('a')]+=1 # 加上当前字母
    #print(sum)
    # 从0 -n 遍历  记录结果  i位置后不同字母  C（2， cnt） =cnt*(cnt-1)//2        
    res=0
    for i in  range(0,n):
        for  j in range(0,26):
            #print(ord(s[i])-ord('a'))
            if  j !=ord(s[i])-ord('a'):
                res+=(sum[i+1][j]*(sum[i+1][j]-1))//2   # 后缀

    print(res) 
sovle()