1759_统计同构子字符串的数目

类型：字符串

• 1759. 统计同构子字符串的数目 💛

  https://leetcode-cn.com/problems/count-number-of-homogenous-substrings/

  ❓ 给你一个字符串 s ，返回 s 中同构子字符串的数目。同构字符串的定义为：由一个字符（可重复）构成的字符串，如 a、aa、aaa 等。

  输入：s = “abbcccaa” 输出：13 解释：同构子字符串如下所列： “a” 出现 3 次。 “aa” 出现 1 次。 “b” 出现 2 次。 “bb” 出现 1 次。 “c” 出现 3 次。 “cc” 出现 2 次。 “ccc” 出现 1 次。 3 + 1 + 2 + 1 + 3 + 2 + 1 = 13

  💡 一次遍历计算三角数

  Untitled

  对于长度为 n 重复字符串来说，其同构数是 n 的三角数，即 1 + 2 + 3 + … + n. 因此我们只需要对 s 进行一次遍历，计算重复字符字串（包括单个字符）的三角数，并累加就可以了。

  class Solution:
      def countHomogenous(self, s: str) -> int:
          if not s: return 0
          max_count = 10 ** 9 + 7
  
          count = 0
          repeat = 1
          for i in range(1, len(s) + 1):
              if i < len(s) and s[i] == s[i - 1]:
                  repeat += 1
              else:
                  count += ((1 + repeat) * repeat // 2)
                  if count >= max_count:
                      count %= max_count
                  repeat = 1
  
          return count

  时间复杂度：O(n)，空间复杂度：O(1)