Consecutive Character Blocks — Problem Statement & Solution Guide

StringsMediumMixed

TimeO(n)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Strings and solve the Consecutive Character Blocks problem optimally.

TopicStrings

PatternMixed

TimeO(n)

SpaceO(1)

Problem Description

Given a string sequence containing only letters (a‑z, A‑Z) and digits (0‑9), count how many maximal contiguous substrings consist of the same character and have length at least two. Each such substring is called a block. Isolated characters (length 1) are not counted. Return the total number of blocks found in sequence.

DSA Pattern Breakdown

"Consecutive Character Blocks"

medium

WHY DOES IT MATTER?

Counting maximal repeated character blocks appears in data compression, log analysis, and DNA sequence processing where run‑length patterns indicate redundancy or anomalies. Mastering this pattern teaches you to recognize when a simple linear scan replaces expensive nested loops.

OPTIMIZATION CHALLENGE

The key insight is that only the boundary between two different characters matters; you never need to revisit earlier characters once a run is closed, collapsing O(n^2) possibilities into a single pass.

REAL-WORLD CONNECTION

Think of a production line where identical items are packaged together; each uninterrupted batch forms a block. Detecting batches quickly prevents bottlenecks, just as the algorithm swiftly identifies character batches in a data stream.

During an interview, write the loop that tracks "prevChar" and "runLen" first, then add the conditional increment of the answer when runLen≥2—this order avoids off‑by‑one errors and makes the code self‑documenting.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem asks for the number of maximal contiguous substrings (blocks) where the same character repeats at least twice. A naïve solution would examine every possible substring, leading to O(n^2) time, which quickly becomes infeasible for strings with millions of characters. The optimal paradigm leverages a single linear scan while maintaining a running count of consecutive identical characters; whenever the current character differs from the previous one, the length of the just‑finished run is evaluated. If the run length is ≥2, it contributes exactly one block to the answer because the definition requires maximal substrings, not overlapping sub‑blocks. This greedy, one‑pass technique is a classic example of run‑length encoding applied to counting, yielding O(n) time and O(1) auxiliary space.

Interview Questions on This Problem

Q1How would you modify the algorithm to also return the starting indices of each block?

During the linear scan keep a variable startIdx that marks the first position of the current run; when the run ends and its length ≥2, push startIdx into a result list before resetting startIdx to the current index.

Q2If the input string can contain Unicode characters beyond ASCII, does the solution change?

No; the algorithm only relies on equality comparison between adjacent characters, which works for any Unicode code point as long as the language’s string representation supports O(1) indexing or iteration.

Q3Can you compute the number of blocks in a streaming fashion where the string is too large to fit in memory?

Yes—process the stream character by character, keep only the previous character and the current run length; when the stream ends, finalize the last run. This uses constant memory and still runs in linear time relative to the stream size.

Examples

Example 1

Input

aabccdee

Output

Explanation: The string splits into groups: "aa" (length 2), "b" (1), "cc" (2), "d" (1), "ee" (2). Only the groups with length ≥2 are counted, giving three blocks.

Example 2

Input

1234445555

Output

Explanation: Grouping yields "1","2","3","444","5555". The blocks "444" and "5555" satisfy the length requirement, so the answer is 2.

Example 3

Input

abcde

Output

Explanation: All characters appear alone, forming groups of length 1. No block meets the minimum size, therefore the result is 0.

Constraints

1 <= sequence.length <= 200000
sequence consists only of characters in the ranges 'a'‑'z', 'A'‑'Z', '0'‑'9'

Optimal Approach & Strategy

Traverse once, maintain the length of the current run of identical characters, and increment the block counter whenever a run ends with length≥2—linear time, constant space.

Brute Force Approach

Generate every possible substring, check if all characters are identical and length≥2, then count distinct maximal ones—quadratic time.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

function countBlocks(sequence) {
    let blocks = 0;
    let i = 0;
    while (i < sequence.length) {
        let j = i + 1;
        while (j < sequence.length && sequence[j] === sequence[i]) j++;
        if (j - i >= 2) blocks++;
        i = j;
    }
    return blocks;
}

const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim();
if (input.length > 0) {
    console.log(countBlocks(input));
}

#include <bits/stdc++.h>
using namespace std;

int countBlocks(const string& sequence) {
    int n = sequence.size();
    int blocks = 0;
    int i = 0;
    while (i < n) {
        int j = i + 1;
        while (j < n && sequence[j] == sequence[i]) ++j;
        if (j - i >= 2) ++blocks;
        i = j;
    }
    return blocks;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    if(!(cin >> s)) return 0;
    cout << countBlocks(s);
    return 0;
}

import java.io.*;
public class Main {
    public static int countBlocks(String sequence) {
        int n = sequence.length();
        int blocks = 0;
        int i = 0;
        while (i < n) {
            int j = i + 1;
            while (j < n && sequence.charAt(j) == sequence.charAt(i)) {
                j++;
            }
            if (j - i >= 2) {
                blocks++;
            }
            i = j;
        }
        return blocks;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        if (s != null) {
            System.out.print(countBlocks(s));
        }
    }
}

def count_blocks(sequence):
    n = len(sequence)
    blocks = 0
    i = 0
    while i < n:
        j = i + 1
        while j < n and sequence[j] == sequence[i]:
            j += 1
        if j - i >= 2:
            blocks += 1
        i = j
    return blocks

if __name__ == "__main__":
    import sys
    data = sys.stdin.read().strip()
    if data:
        print(count_blocks(data))

function countBlocks(sequence) {
    let blocks = 0;
    let i = 0;
    while (i < sequence.length) {
        let j = i + 1;
        while (j < sequence.length && sequence[j] === sequence[i]) j++;
        if (j - i >= 2) blocks++;
        i = j;
    }
    return blocks;
}

const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim();
if (input.length > 0) {
    console.log(countBlocks(input));
}

Asked in Top Tech Interviews

MicrosoftSalesforce

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.