LeetCode 1759: Count Number of Homogenous Substrings Solution

Master LeetCode problem 1759 (Count Number of Homogenous Substrings), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1759. Count Number of Homogenous Substrings

Medium

Math String

Problem Explanation

Explanation

To solve this problem, we can iterate through the input string s while keeping track of the current character and the count of consecutive occurrences of that character. For each character, we can calculate the number of homogenous substrings ending at that character. The total number of homogenous substrings will be the sum of these counts.

Algorithmic Idea

Initialize variables result and count to 0.
Iterate through the characters of the input string s.
For each character:
- If it is the same as the previous character, increment the count.
- Otherwise, calculate the number of homogenous substrings ending at the current character using the formula (count * (count + 1)) / 2.
- Add this count to the result.
After the loop, calculate the number of homogenous substrings for the last character using the same formula.
Return the result modulo 10^9 + 7.

Time Complexity

The time complexity of this approach is O(n), where n is the length of the input string s.

Space Complexity

The space complexity of this approach is O(1) as we are using a constant amount of extra space.

Solution Code

class Solution {
    public int countHomogenous(String s) {
        int mod = 1000000007;
        int result = 0;
        int count = 0;

        for (int i = 0; i < s.length(); i++) {
            if (i == 0 || s.charAt(i) == s.charAt(i - 1)) {
                count++;
            } else {
                result = (result + count * (count + 1) / 2) % mod;
                count = 1;
            }
        }

        result = (result + count * (count + 1) / 2) % mod;
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1759 (Count Number of Homogenous Substrings)?

This page provides optimized solutions for LeetCode problem 1759 (Count Number of Homogenous Substrings) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1759 (Count Number of Homogenous Substrings)?

The time complexity for LeetCode 1759 (Count Number of Homogenous Substrings) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1759 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1759 in Java, C++, or Python.

Back to LeetCode Solutions