在刷题中过年 1930 ～ 长度为 3 的不重复 substring

基本信息

• 题号：1930
• 题厂：亚麻，脸书，谷歌
• 难度系数：中

找出一个字符串中所有不重复、长度为 3 的 palindromic substring 字符串个数。。。

• palindromic：即对称的字符串，例如 aba，bab。。。
• subsequence：比原数组短，但是保持顺序一致。。。如 abcc 是 aabbcccc 的 subsequence

s = "aabca"

返回 3
长度为 3 满足 subsequence palindromic 标准的有 aba，aaa，aca

解题思路

1. 要找 palindromic，一个比较常规的方法思路是，以一个元素为中心，向左右两边扩散。。。。这样比较麻烦。。。。
2. 关于这道题，要抓住题目只找长度为 3 的 palindromic。abba 虽然也是 palindromic，但是长度为 4 所以不需要。
3. 既然是长度为 3，那必然满足一个 pattern，那就是左右字符相同，中间随意。
4. 沿着以上思路，我们以一个字符为中心，如果它的左右分别有相同的字符出现，即可满足条件。。。。。想到这里可以明白，此处需要使用 set。。。。。。

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        # 初始化 res 用于返回，元素配对模式为 「中间元素：两边元素」
        res = set() 
        # 同时初始化左右 set，右边用 hashmap 记录，配对模式为 「元素：个数」
        left = set()
        right = collections.Counter(s) # generate hashmap
        
        # 遍历数组，如果当前元素在右边 hashmap 中，hashmap 对应元素所剩数量减 1；如果剩余数量为 0，就把该元素从 hashmap 中 pop 出去
        for i in range(len(s)):
            if s[i] in right:
                right[s[i]] -= 1
            
            if right[s[i]] == 0:
                right.pop(s[i])

            # 左右两边如何检测？？采用处理字符串中常用 ascii 方面
            # 如果我们在左右 set 中都找到了相同元素，则发现了一个「长度为 3 又是 palindromic 的 subsequence」，需要往 res 里添加
            for j in range(26):
                c = chr(ord("a") + j)
                if c in left and c in right:
                    res.add((s[i], c))

            # 添加完 还要把当前元素加到左边 set，以便下一次遍历
            left.add(s[i])

        # 返回 res 的长度，即满足所有条件又不重复的数量。。。。
        return len(res)

Constraints

• 3 <= s.length <= 105
• s consists of only lowercase English letters.

做题前要向考官讨论字符串包括什么特色，字符串只有 26 个小写英文字母出现是可以使用 ascii 码解体的重点。。。。。。

测试

• 长度为 3 没有了 palindromic 时
• 长度为 3 有 pandlindromic 时
• 长度大于 3 有很多重复字符时
• ……

Big O

• 时间复杂度：O（26n）
• 空间复杂度：O（n）

总结

• 简化时间复杂度的关键在于要抓住题目特色：长度为 3， 元素只有 26 个小写英文字符……
• palindromic 是字符串，数组问题常考高频话题，各种变形……