【LeetCode】 1759. Count Number of Homogenous Substrings

Description

Given a string s, return the number of homogenous substrings of s. Since the answer may be too large, return it modulo 10^9 + 7.
A string is homogenous if all the characters of the string are the same.
A substring is a contiguous sequence of characters within a string.

Constraints:

• 1 <= s.length <= 105
• s consists of lowercase letters.

給予一個字串 s，回傳 s 的同質子字串的數量。因為答案可能太大，回傳前請對 10^9 + 7 取餘數。
一個字串如果所有的字元都是一樣的，我們稱該字串同質。
子字串是指一個字串中任意連續的字元序列。

限制：

• 1 <= s.length <= 105
• s 只會包含小寫字母。

Example:

Example 1:

Input: s = "abbcccaa"
Output: 13
Explanation: The homogenous substrings are listed as below:
"a"   appears 3 times.
"aa"  appears 1 time.
"b"   appears 2 times.
"bb"  appears 1 time.
"c"   appears 3 times.
"cc"  appears 2 times.
"ccc" appears 1 time.
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13.

Example 2:

Input: s = "xy"
Output: 2
Explanation: The homogenous substrings are "x" and "y".
Example 3:

Input: s = "zzzzz"
Output: 15

Solution

• 為了降低運算量，可以先想想同質字串的長度與答案之間是否有辦法寫成數學式
• 假設今天有一同質字串長度為 n
  • 可以視為 1 個長度為 n 的同質字串
  • 可以視為 2 個長度為 n - 1 的同質字串
  • 可以視為 3 個長度為 n - 2 的同質字串
  • …
  • 可以視為 n 個長度為 1 的同質字串
• 全部加總起來，得到 1 + 2 + 3 ... + n - 1 + n 個同質字串
  • 使用公式計算總合，得到 (1 + n) * n / 2
• 因此我們只需要看每一段長度最長的同質字串，並將其加總即可
  • 例如 aaabb，我們只須分別算 aaa 和 bb 即可
• 實作上請注意型別，因為大小可能很大，需要使用 long long 等型別去儲存答案

Code

class Solution {
public:
    int countHomogenous(string s) {
        long long count = 0;
        long long ans = 0;
        char prev = '1';
        for(int i = 0; i < s.size(); i++)
        {
            if(s[i] == prev)
                count++;
            else
            {
                ans += count * (count + 1) / 2;
                count = 1;
            }
            prev = s[i];
        }
        ans += count * (count + 1) / 2;
        return ans % ((int)pow(10, 9) + 7);
    }
};

tags: LeetCode C++