小美定义一个字符串的权值为:其长度为3的回文子序列数量。例如,"abcaabcaabca"的权值为222,因为包含 两个回文子序列"abaabaaba"和"acaacaaca"。
暴力思路:对于一个位置i,我们考虑往前找所有s[i] == s[j] 的位置j。那么[j+1,i-1]这一段的任意一个字符都可以被选择,也就是j对i的答案贡献就是j - i - 1。也就是找到所有的j,去求和。
那么位置i的答案是:
发现第一个求和式的内容(i - 1) 与 j无关:
本题属于以下题库,请选择所需题库进行购买
ScanQRCodePrompt
GoToPasswordLoginPrompt