package LeetCode_1759

/**
 * 1759. Count Number of Homogenous Substrings
 * https://leetcode.com/problems/count-number-of-homogenous-substrings/
 * 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.

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

Constraints:
1. 1 <= s.length <= 10^5
2. s consists of lowercase letters.
 * */
class Solution {
    /*
    Solution: keep counting the same char then update sameCharCount and result,
    and reset sameCharCount=1 when current char not equal last char;
    Time:O(n), Space:O(1)
    * */
    fun countHomogenous(s: String): Int {
        val mod = 1000000007
        var lastChar: Char? = null
        var result = 0
        var sameCharCount = 0
        for (c in s) {
            if (lastChar == null || lastChar == c) {
                sameCharCount++
            } else {
                sameCharCount = 1
            }
            lastChar = c
            result = (result + sameCharCount) % mod
        }
        return result
    }
}