1. Arithmetic Sequence

Intuition

The string can be split into consecutive groups of identical characters. For each group of length L, the number of substrings containing only that character follows the arithmetic sequence formula: 1 + 2 + 3 + ... + L = L*(L+1)/2. We scan through the string, identify each group, and sum up the contributions.

Algorithm

1. Use two pointers, left and right, both starting at 0.
2. Move right through the string until a different character is found or the end is reached.
3. When a group ends (character changes or string ends):
   • Calculate the length of the group as (right - left).
   • Add the arithmetic sum: (length * (length + 1)) / 2 to the total.
   • Move left to right to start the next group.
4. Return the total count.

class Solution:
    def countLetters(self, S: str) -> int:
        total = left = 0

        for right in range(len(S) + 1):
            if right == len(S) or S[left] != S[right]:
                len_substring = right - left
                # more details about the sum of the arithmetic sequence:
                # https://en.wikipedia.org/wiki/Arithmetic_progression#Sum
                total += (1 + len_substring) * len_substring // 2
                left = right

        return total

Time & Space Complexity

• Time complexity: $O(N)$

• Space complexity: $O(1)$ constant space

Where $N$ is the length of the input string s.

---

2. Dynamic Programming

Intuition

For each position i, we can compute how many valid substrings end at that position. If the character at position i matches the previous character, the count equals the previous count plus 1 (we extend all previous substrings and add one new single-character substring). Otherwise, only the single character itself forms a valid substring. The total is the sum across all positions.

Algorithm

1. Create an array substrings where substrings[i] represents valid substrings ending at index i.
2. Initialize substrings[0] = 1 and total = 1.
3. For each position i from 1 to n-1:
   • If s[i] equals s[i-1], set substrings[i] = substrings[i-1] + 1.
   • Otherwise, set substrings[i] = 1.
   • Add substrings[i] to total.
4. Return the total count.

class Solution:
    def countLetters(self, S: str) -> int:
        total = 1
        substrings = [0] * len(S)
        substrings[0] = 1

        for i in range(1, len(S)):
            if S[i - 1] == S[i]:
                substrings[i] = substrings[i-1] + 1
            else:
                substrings[i] = 1

            total += substrings[i]

        return total

Time & Space Complexity

• Time complexity: $O(N)$

• Space complexity: $O(N)$

Where $N$ is the length of the input string s.

---

3. Dynamic Programming (Optimized)

Intuition

Since we only need the previous value to compute the current one, we can optimize space by using a single variable instead of an array. This variable (count) tracks the count of valid substrings ending at the current position.

Algorithm

1. Initialize total = 1 and count = 1 (for the first character).
2. For each position i from 1 to n-1:
   • If s[i] equals s[i-1], increment count by 1.
   • Otherwise, reset count to 1.
   • Add count to total.
3. Return the total count.

class Solution:
    def countLetters(self, S: str) -> int:
        total = 1
        count = 1
        
        for i in range(1, len(S)):
            if S[i] == S[i-1]:
                count += 1
            else:
                count = 1

            total += count

        return total

Time & Space Complexity

• Time complexity: $O(N)$

• Space complexity: $O(1)$ constant space

Where $N$ is the length of the input string s.

---

Common Pitfalls

Using Wrong Formula for Counting Substrings

For a group of L identical consecutive characters, the number of valid substrings is L * (L + 1) / 2, not L or L * L. This arithmetic sum counts substrings of lengths 1, 2, 3, ..., L.

# Wrong: Only counts substrings of length 1
total += length

# Wrong: Overcounts
total += length * length

# Correct: Sum of 1 + 2 + ... + L
total += length * (length + 1) // 2

Forgetting to Process the Last Group

When iterating through the string to find groups of identical characters, the last group may not be processed if the loop only triggers on character changes. Ensure the final group is counted either by extending the loop to len(s) + 1 or by handling it after the loop ends.