No Consecutive Digit Substring Count

Count the number of substrings in a digit string where no two consecutive digits are identical.

Understand the Problem

Problem Statement

Orlando wants to count the number of substrings in a digit string S (containing only digits 0-9) where no two consecutive digits in the substring are repeated.

A substring is considered invalid if it contains two identical digits next to each other. The task is to count all valid substrings of the given string.

For example:

For input "121", the valid substrings are: "1", "2", "1", "12", "21", and "121". There are 6 valid substrings.
For input "112", the valid substrings are: "1", "1", "2", "11" (invalid), "12", and "112" (invalid). Only 4 are valid.

Constraints

1 ≤ |S| ≤ 10,000 (where |S| is the length of the string)
S contains only digits from '0' to '9'
The result may be large, so ensure your algorithm is efficient

Examples

Example 1

Input

Output

Explanation

All substrings are valid: "1", "2", "1", "12", "21", "121". Total = 6.

Example 2

Input

Output

Explanation

Valid substrings: "1", "1", "2", "12". Invalid: "11", "112". Total = 4.

Example 3

Input

Output

Explanation

All substrings are valid since all digits are different: "1", "2", "3", "12", "23", "123". Total = 6.

Solution

#include <stdio.h>
#include <string.h>

int main() {
    char s[10001];
    fgets(s, sizeof(s), stdin);
    
    // Remove newline if present
    int len = strlen(s);
    if (s[len-1] == '\n') {
        s[len-1] = '\0';
        len--;
    }
    
    long long total = 0;
    int current_len = 1;
    
    // Start from second character
    for (int i = 1; i <= len; i++) {
        // If we're at the end or current char equals previous char
        if (i == len || s[i] == s[i-1]) {
            // Add substrings for current segment
            total += (long long)current_len * (current_len + 1) / 2;
            current_len = 1;
        } else {
            current_len++;
        }
    }
    
    printf("%lld\n", total);
    return 0;
}

Time:O(n) - Single pass through the string

Space:O(1) - Only using a few variables regardless of input size

Approach:

1. Read the input string using fgets to handle potentially long strings safely.

2. Remove trailing newline character if present.

3. Initialize total count and current segment length.

4. Iterate through the string starting from index 1.

5. If current character equals previous character (or we reached end), calculate substrings for the completed segment using the formula n*(n+1)/2 and reset segment length.

6. Otherwise, extend the current valid segment.

7. Use long long to handle large results from the formula.

Visual Explanation

Loading diagram...

All Problems