# 【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++`