Leetcode # 2981. Find Longest Special Substring That Occurs Thrice I

Problem

https://leetcode.com/problems/find-longest-special-substring-that-occurs-thrice-i

Solution / First Try

• 第 5 行的s + "*"是為了能在結尾時再做一次判斷
• aaaaa代表包含 1 個aaaaa, 2 個aaaa, 3 個aaa, 4 個aa, 5 個a

Time Complexity: O(len(s) ** 2)
Space Complexity: O(len(s) ** 2)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def maximumLength(self, s: str) -> int:
    start = 0
    counter = Counter()
    for i, c in enumerate(s + "*"):
      if c == s[start]: continue
      
      sub_s_len = i - start + 1
      for j in range(1, sub_s_len):
        counter[s[start] * j] += sub_s_len - j

      start = i
      
    lss_len = -1
    for special_sub_s, n in counter.most_common():
      if n < 3: break
      lss_len = max(lss_len, len(special_sub_s))

    return lss_len

Last Updated on 2024/12/11 by A1go