发表于 2024.05.29

• 朴素的做法是使用双重循环，枚举并计数所有的的特殊子字符串(即所有字符相同，当遇到不一样的字符时终止内层循环)，但这样会超时。我们可以通过滑动窗口的方式节省遍历连续重复字符的时间，维护当前字符last_ch及其连续重复次数recessive_cnt，并使用二维数组ch_recessive_counts[i][j]维护第i个小写字母连续组成j次的子串计数。然后在每次循环最后，更新计数信息ch_recessive_counts[last_ch][j] += 1 (1 <= j <= recessive_cnt)。然后再更新最长且出现至少三次的子串即可。

  class Solution:
      def maximumLength(self, s: str) -> int:
          ch_recessive_counts = [[0] * 51 for _ in range(26)]
  
          last_ch = ''
          recessive_cnt = 0
  
          max_len = -1
  
          for i, ch in enumerate(s):
              if last_ch == ch:
                  recessive_cnt += 1
              else:
                  last_ch = ch
                  recessive_cnt = 1
      
              ch_index = ord(ch) - ord('a')
              for j in range(1, recessive_cnt + 1):
                  ch_recessive_counts[ch_index][j] += 1
                  # 更新结果
                  if ch_recessive_counts[ch_index][j] >= 3 and j > max_len:
                      max_len = j
          return max_len

  超时的版本：

  class Solution:
      def maximumLength(self, s: str) -> int:
          cnt_map = defaultdict(int)
          max_len = -1
          for i, ch in enumerate(s):
              for l in range(1, len(s) - i + 1):
                  if s[i + l - 1] != ch:
                      break
                  sub = s[i:i + l]
                  cnt_map[sub] += 1
                  if cnt_map[sub] >= 3 and len(sub) > max_len:
                      max_len = len(sub)
          return max_len

• LC 题目链接