Count Substrings with Only One Distinct Letter

Easy
516.

Count Substrings with Only One Distinct Letter

Count Substrings with Only One Distinct Letter is an easy coding problem on strings and math, asked in Amazon and Adobe interviews.

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

Substrings are counted by position, so identical substrings occurring at different places count separately.

Example 1

Input
s = "aaaba"
Output
8
Explanation
"aaa" contributes 6 substrings, plus "b" and the trailing "a".

Example 2

Input
s = "aaaaaaaaaa"
Output
55
Explanation
A run of 10 gives 10·11/2 = 55.

Example 3

Input
s = "abc"
Output
3

Constraints

  • 1 <= s.length <= 1000
  • s consists of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var countLetters = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Substrings with Only One Distinct Letter — Solution

Count Substrings with Only One Distinct Letter solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Count Substrings with Only One Distinct Letter is an easy coding problem on strings and math, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Strings, Math
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

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

Substrings are counted by position, so identical substrings occurring at different places count separately.

Example 1

Input: s = "aaaba"
Output: 8
Explanation: "aaa" contributes 6 substrings, plus "b" and the trailing "a".

Example 2

Input: s = "aaaaaaaaaa"
Output: 55
Explanation: A run of 10 gives 10·11/2 = 55.

Example 3

Input: s = "abc"
Output: 3

Constraints

  • 1 <= s.length <= 1000
  • s consists of lowercase English letters.

Hints for Count Substrings with Only One Distinct Letter

  1. Hint 1

    Every valid substring lies entirely inside a maximal run of equal characters.

  2. Hint 2

    A run of length k contains k(k+1)/2 substrings.

  3. Hint 3

    Split the string into runs and sum that formula over them.

How to solve Count Substrings with Only One Distinct Letter

A substring with one distinct letter is a contiguous block of identical characters, so it must sit inside a maximal run. Counting the substrings of each run and summing gives the answer directly.

Approach

  1. Scan the string, extending a run counter while consecutive characters match.
  2. When the run ends (or the string does), add run * (run + 1) / 2 to the total.
  3. Reset the run counter and continue.

Why it works

A run of length k has exactly one substring of length k, two of length k-1, …, k of length 1 — a triangular number, k(k+1)/2. Runs are disjoint, so their counts simply add.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Forgetting to flush the final run drops every substring in the last block.
  • Enumerating all substrings is O(n²) and unnecessary.
  • k(k+1)/2 for k = 1000 is 500,500 — comfortably in range, but the product k*(k+1) should still be computed before the division.

Reference solution

Python

def countLetters(s: str) -> int:
    total = 0
    run = 1
    for i in range(1, len(s) + 1):
        if i < len(s) and s[i] == s[i - 1]:
            run += 1
        else:
            total += run * (run + 1) // 2
            run = 1
    return total

Java

public static int countLetters(String s) {
    long total = 0;
    int run = 1;
    for (int i = 1; i <= s.length(); i++) {
        if (i < s.length() && s.charAt(i) == s.charAt(i - 1)) run++;
        else {
            total += (long) run * (run + 1) / 2;
            run = 1;
        }
    }
    return (int) total;
}

C++

int countLetters(string s) {
    long long total = 0;
    int run = 1;
    for (int i = 1; i <= (int) s.size(); i++) {
        if (i < (int) s.size() && s[i] == s[i - 1]) run++;
        else {
            total += (long long) run * (run + 1) / 2;
            run = 1;
        }
    }
    return (int) total;
}

JavaScript

var countLetters = function(s) {
    let total = 0, run = 1;
    for (let i = 1; i <= s.length; i++) {
        if (i < s.length && s.charAt(i) === s.charAt(i - 1)) run++;
        else {
            total += (run * (run + 1)) / 2;
            run = 1;
        }
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings