<p>Given a string <code>s</code>, return <em>the number of <strong>homogenous</strong> substrings of </em><code>s</code><em>.</em> Since the answer may be too large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>A string is <strong>homogenous</strong> if all the characters of the string are the same.</p>

<p>A <strong>substring</strong> is a contiguous sequence of characters within a string.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abbcccaa&quot;
<strong>Output:</strong> 13
<strong>Explanation:</strong> The homogenous substrings are listed as below:
&quot;a&quot;   appears 3 times.
&quot;aa&quot;  appears 1 time.
&quot;b&quot;   appears 2 times.
&quot;bb&quot;  appears 1 time.
&quot;c&quot;   appears 3 times.
&quot;cc&quot;  appears 2 times.
&quot;ccc&quot; appears 1 time.
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;xy&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> The homogenous substrings are &quot;x&quot; and &quot;y&quot;.</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;zzzzz&quot;
<strong>Output:</strong> 15
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s</code> consists of lowercase letters.</li>
</ul>

// class Solution {
// public:
//     int mod = 1e9+7;
// void computeLPSArray(string& t, int* lps) {
//     int m = t.length();
//     lps[0] = 0;
//     int len = 0;
//     int i = 1;
//     while (i < m) {
//         if (t[i] == t[len]) {
//             len++;
//             lps[i] = len;
//             i++;
//         } else {
//             if (len != 0) {
//                 len = lps[len - 1];
//             } else {
//                 lps[i] = 0;
//                 i++;
//             }
//         }
//     }
// }

// int cnt(string& s, string t) {
//     long long count = 0;
//     int n = s.length();
//     int m = t.length();
//     int lps[m];
//     computeLPSArray(t, lps);
//     int i = 0;
//     int j = 0;
//     while (i < n) {
//         if (s[i] == t[j]) {
//             i++;
//             j++;
//         }
//         if (j == m) {
//             count = (count + 1) % mod;
//             j = lps[j - 1];
//         } else if (i < n && s[i] != t[j]) {
//             if (j != 0)
//                 j = lps[j - 1];
//             else
//                 i++;
//         }
//     }
//     return count;
// }

//     int countHomogenous(string s) {
//         unordered_map<char , int> mp;
//         int n = s.size(); mp[s[0]] += 1;

//         for(int i = 1 ; i<n ; i++){
//             char c = s[i];
//             if(mp[c] == 0 || c == s[i-1]) mp[c]+=1;
//         }
//         int ans = 0;

//         for(auto it : mp){
//             string st = "";
//             for(int i = 1 ; i<= it.second ; i++){
//                 st.push_back(it.first);
//                 ans = (ans + cnt(s , st)%mod)%mod;
//             }
//         }

//         return ans%mod;
//     }
// };

class Solution {
public:
    int mod = 1e9 + 7;

    // Precomputed LPS arrays for each substring length
    unordered_map<string, int*> lpsArrays;

    void computeLPSArray(string& t, int* lps) {
        int m = t.length();
        lps[0] = 0;
        int len = 0;
        int i = 1;
        while (i < m) {
            if (t[i] == t[len]) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
    }

    int cnt(string& s, string t) {
        int* lps;
        if (lpsArrays.find(t) != lpsArrays.end()) {
            // Use precomputed LPS array
            int* lps = lpsArrays[t];
        } else {
            int m = t.length();
            int* lps = new int[m];
            computeLPSArray(t, lps);
            lpsArrays[t] = lps;
        }

        long long count = 0;
        int n = s.length();
        int m = t.length();
        int i = 0;
        int j = 0;
        while (i < n) {
            if (s[i] == t[j]) {
                i++;
                j++;
            }
            if (j == m) {
                count = (count + 1) % mod;
                j = lps[j - 1];
            } else if (i < n && s[i] != t[j]) {
                if (j != 0)
                    j = lps[j - 1];
                else
                    i++;
            }
        }
        return count;
    }

    int countHomogenous(string s) {
        int n = s.size();
        int ans = 0;

        // Dynamic Programming approach
        vector<int> dp(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            if (i == 1 || s[i - 1] != s[i - 2]) {
                dp[i] = 1;
            } else {
                dp[i] = (dp[i - 1] + 1) % mod;
            }
            ans = (ans + dp[i]) % mod;
        }

        return ans;
    }
};

19100