Introduction

In this blog post, we will explore how to solve the LeetCode problem "1759" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Given a string s, return the number of homogenous substrings of s. Since the answer may be too large, return it modulo 109 + 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 <= s.length <= 105 s consists of lowercase letters.

Explanation

Here's the breakdown of the approach and the Python code:

• High-Level Approach:

  • Iterate through the string, identifying contiguous homogenous blocks (sequences of the same character).
  • For each homogenous block of length n, the number of homogenous substrings is the sum of integers from 1 to n, which can be calculated as n * (n + 1) // 2.
  • Accumulate the counts of homogenous substrings and apply the modulo operator to prevent overflow.

• Complexity:

  • Runtime Complexity: O(n), where n is the length of the string.
  • Storage Complexity: O(1)

Code

    def countHomogenous(s: str) -> int:
    """
    Counts the number of homogenous substrings of a string modulo 10^9 + 7.

    Args:
        s: The input string.

    Returns:
        The number of homogenous substrings modulo 10^9 + 7.
    """
    MOD = 10**9 + 7
    count = 0
    i = 0
    while i < len(s):
        j = i
        while j < len(s) and s[i] == s[j]:
            j += 1
        length = j - i
        count = (count + length * (length + 1) // 2) % MOD
        i = j
    return count