Count Substrings with Only One Distinct Letter

easy string counting two pointers

Problem

Given a string s, return the number of substrings that have only one distinct letter. A substring is a contiguous slice of s, and we want those where every character is identical.

Inputs = "aaaba"

Output8

Runs are "aaa", "b", "a". A run of length n yields n·(n+1)/2 substrings: 3·4/2 = 6, plus 1, plus 1 = 8.

s (letters only)

def count_letters(s):
    total = 0
    run = 0
    for i, ch in enumerate(s):
        if i > 0 and ch == s[i - 1]:
            run += 1
        else:
            run = 1
        total += run
    return total

function countLetters(s) {
  let total = 0;
  let run = 0;
  for (let i = 0; i < s.length; i++) {
    if (i > 0 && s[i] === s[i - 1]) {
      run += 1;
    } else {
      run = 1;
    }
    total += run;
  }
  return total;
}

class Solution {
    public int countLetters(String s) {
        int total = 0, run = 0;
        for (int i = 0; i < s.length(); i++) {
            if (i > 0 && s.charAt(i) == s.charAt(i - 1)) {
                run += 1;
            } else {
                run = 1;
            }
            total += run;
        }
        return total;
    }
}

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

Explanation

A substring with only one distinct letter must sit entirely inside a run of identical characters. A run of length L contains L·(L+1)/2 such substrings, and this solution adds them up in a single pass without ever computing that formula directly.

We keep a run counter for the length of the current run ending at the position we are on. When s[i] equals the previous character, the run grows: run += 1. When it differs, a new run starts and we reset run = 1.

The clever part is adding run to total at every index. The reason: every position i ends exactly run single-letter substrings (the ones starting anywhere within the current run and finishing at i). Summing run over the whole string therefore counts them all.

Adding 1, 2, 3, ... across a run is just the triangular number L·(L+1)/2, so this running sum produces the same result with no special math.

Example: "aaaba". The runs add 1+2+3 for "aaa", then 1 for "b", then 1 for the final "a", giving 6+1+1 = 8.

Time: O(n) Space: O(1)