Count Substrings with Only One Distinct Letter Python/Java solution

Most implementations iterate through the string while tracking the length of the current identical-character run. Each time the run ends, add k * (k + 1) / 2 to the result. The same logic works in Python, Java, C++, and Go with O(n) time and O(1) space.

How to solve Count Substrings with Only One Distinct Letter in O(n)?

Traverse the string and track the length of the current block of identical characters. When a block ends, compute the number of substrings using k * (k + 1) / 2 and add it to the result. Continue scanning the string and repeat for each run, resulting in a single linear pass.

What is the best approach for Count Substrings with Only One Distinct Letter?

The optimal approach groups consecutive identical characters and counts substrings using the formula k * (k + 1) / 2 for each run of length k. This works because every substring inside that run contains the same character. The algorithm scans the string once, giving O(n) time complexity and O(1) space.

Is Count Substrings with Only One Distinct Letter asked at Google/Amazon/Meta?

Substring counting and sliding window patterns frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying concepts—string traversal, run-length counting, and two-pointer techniques—are common interview topics.

What data structure is used in Count Substrings with Only One Distinct Letter?

The solution primarily uses simple variables and string traversal. No complex data structures are required. The logic relies on counting consecutive characters, often implemented with counters or two pointers.

What is the time complexity of Count Substrings with Only One Distinct Letter?

The optimal solution runs in O(n) time where n is the length of the string. You iterate through the string once while tracking the length of consecutive identical characters. Space complexity is O(1) since only a few counters are needed.

Description Hints 3 Solution Video 6:00

1180. Count Substrings with Only One Distinct Letter

Q: Is Count Substrings with Only One Distinct Letter easy or hard?

Count Substrings with Only One Distinct Letter is classified as an Easy problem on LeetCode with an acceptance rate around 80%. The key insight is recognizing that consecutive identical characters form a combinatorial pattern, allowing a simple O(n) solution.

Easy80.9% acceptance1 companyPremium elsewhere, free here

Given a string s, return the number of substrings that have only one distinct letter.

Example 1:

Input: s = "aaaba"
Output: 8
Explanation: The substrings with one distinct letter are "aaa", "aa", "a", "b".
"aaa" occurs 1 time.
"aa" occurs 2 times.
"a" occurs 4 times.
"b" occurs 1 time.
So the answer is 1 + 2 + 4 + 1 = 8.

Example 2:

Input: s = "aaaaaaaaaa"
Output: 55

Constraints:

1 <= s.length <= 1000
s[i] consists of only lowercase English letters.

Asked at 1 company

Virtu Financial

Topics

Math String

Hints open one at a time

Hint 1

What if we divide the string into substrings containing only one distinct character with maximal lengths?

Hint 2

Now that you have sub-strings with only one distinct character, Try to come up with a formula that counts the number of its sub-strings.

Hint 3

Alternatively, Observe that the constraints are small so you can use brute force.

6:00

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"aaaba"

Input

"aaaaaaaaaa"

Your code is saved on this device.Solution