LeetCode中等题：长度为3的回文子序列计数解法调试求助

问题描述 #

LeetCode中等难度题目：给定字符串s，返回s中作为子序列的长度为3的唯一回文串的数量。
注意：即使有多种方式得到同一个子序列，也仅计数一次。

• 回文串：正读和反读都相同的字符串。
• 子序列：从原字符串中删除部分字符（可删除零个）后，不改变剩余字符相对顺序得到的新字符串。

解题思路 #

找到每个字符的首次和末次出现位置，统计两者之间的不同字符数，同时需考虑如"aaa"这类由相同字符构成的回文情况。

实现代码 #

func countPalindromicSubsequence(s string) int {
    p := make(map[rune][2]int)
    o := make(map[rune]int)
    total := 0
    for i, v := range s {
        o[v]++
        _, ok := p[v]
        if !ok {
            // 首次记录该字符的索引
            s :=[2]int{i,0}
            p[v]  = s
            
        }else {
            s := p[v] 
            s[1] = i
            p[v]  = s
        }
    }

    for k,v := range p {
        if v[1] == 0 {
            continue
        }
        if o[k] >= 3 {
            total++
        }
        // 统计中间可构成回文的字符
        for l, value := range p {
            if l != k && ((value[0] > v[0] && value[0] < v[1]) || (value[1] > v[0] && value[1] < v[1])){
                total ++
            }
        }
        
    }
    
   return total
}

代码说明 #

• map p：存储字符串中出现的字符及其首次、末次出现索引，若字符仅出现一次，第二个索引保持为0。
• map o：存储每个字符的出现次数，例如字符a出现5次时，p['a']为{首次索引, 末次索引}，o['a']为5。
• 遍历map p时，通过v[1] == 0判断字符是否出现至少两次，只有出现至少两次的字符才可能构成长度为3的回文。
• 再次遍历map p，统计出现在当前字符首次和末次索引之间的其他字符，这些字符可与当前字符构成ABA型的长度为3的回文。
• 通过map o判断是否存在AAA型的回文（即字符出现次数≥3）。

遇到的问题 #

上述解法在测试用例"tlpjzdmtwderpkpmgoyrcxttiheassztncqvnfjeyxxp"上执行失败，目前调试无果，寻求帮助。

内容的提问来源于stack exchange，提问作者nrs16