Alternating Character Substrings — Problem Statement & Solution Guide

StringsMediumMixed

TimeO(n)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Strings and solve the Alternating Character Substrings problem optimally.

TopicStrings

PatternMixed

TimeO(n)

SpaceO(1)

Problem Description

Given a string sequence that contains only the characters 'V' and 'N', compute the total number of substrings whose consecutive characters strictly alternate. A substring of length one is always considered alternating. Return the count as a 64‑bit integer.

DSA Pattern Breakdown

"Alternating Character Substrings"

medium

WHY DOES IT MATTER?

Counting alternating substrings is a classic example of converting a global combinatorial problem into a local, incremental one. Mastering this pattern teaches you how to turn O(n²) enumeration into O(n) scanning, a skill that appears in many string‑processing and array‑analysis problems.

OPTIMIZATION CHALLENGE

The breakthrough is realizing that the number of valid substrings ending at position i depends solely on whether s[i] matches s[i‑1]. By storing only the length of the current alternating run, we avoid any extra data structures and achieve constant space.

REAL-WORLD CONNECTION

In network protocols, packets often alternate between control and data frames to avoid consecutive identical frames that could cause synchronization issues. Detecting or generating such alternating sequences efficiently mirrors the substring counting technique.

During an interview, explicitly state the invariant ("currLen = length of longest alternating suffix ending at i") before the loop, then show how the invariant updates in O(1) time. This demonstrates clear reasoning and avoids off‑by‑one bugs.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

An alternating substring is a contiguous segment of the input where every adjacent pair of characters differs (i.e., "VN" or "NV"). The key observation is that for each position i we can compute the number of alternating substrings that end at i by looking only at the previous character: if s[i] != s[i-1] then every alternating substring ending at i‑1 can be extended by s[i], plus the single‑character substring s[i] itself; otherwise only the single character forms a valid alternating substring. By maintaining a running count of the length of the current alternating run, we can accumulate the total number of alternating substrings in a single left‑to‑right pass. A naive solution would enumerate all O(n²) possible substrings and check each for the alternating property, which quickly becomes infeasible for strings of length up to 10⁶ or more. The optimal paradigm leverages dynamic programming (or a simple greedy count) to achieve O(n) time and O(1) extra space, making it suitable for large inputs and fitting the 64‑bit integer requirement.

Interview Questions on This Problem

Q1How would you compute the total number of alternating substrings in a string consisting only of 'V' and 'N' in linear time?

Iterate once through the string while keeping a variable currLen that stores the length of the current alternating run. If the current character differs from the previous one, increment currLen; otherwise reset it to 1. Add currLen to a global answer after each step. This yields O(n) time and O(1) space.

Q2What modifications are needed if the alphabet expands to more than two characters, e.g., 'A', 'B', 'C'?

The same technique works: a substring is alternating if each adjacent pair is different, regardless of the total alphabet size. The algorithm still only checks s[i] != s[i-1] to decide whether to extend the current run, so no structural changes are required.

Q3Why does the answer fit in a 64‑bit integer even for the maximum input size (e.g., 10⁶ characters)?

The worst‑case scenario is a perfectly alternating string where the number of substrings equals n·(n+1)/2. For n = 10⁶ this value is about 5·10¹¹, which is well below 2⁶³‑1, the maximum of a signed 64‑bit integer.

Examples

Example 1

Input

VNVN

Output

Explanation: The whole string is alternating, length 4. Number of alternating substrings = 4*5/2 = 10.

Example 2

Input

VVN

Output

Explanation: Positions 1‑1 form a length‑1 alternating substring. Positions 2‑3 form "VN", an alternating segment of length 2, contributing 2*3/2 = 3 substrings. Total = 1+3 = 4.

Example 3

Input

NNNN

Output

Explanation: No two adjacent characters differ, so only the four single‑character substrings are valid.

Constraints

1 <= sequence.length <= 200000
sequence consists exclusively of 'V' and 'N' characters
Result fits in a signed 64‑bit integer
Expected time complexity O(n)
Expected auxiliary space O(1)

Optimal Approach & Strategy

Maintain a single counter for the length of the current alternating suffix while iterating the string. Add this counter to the answer at each step, yielding an O(n) time and O(1) extra space solution.

Brute Force Approach

Generate every possible substring (i, j) and check whether each adjacent pair alternates; this requires O(n²) substrings and O(n) work per check, leading to O(n³) time in the worst case. Such an approach quickly exceeds time limits for large strings.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

function alternatingSubstrings(s) {
    const n = s.length;
    let count = n; // substrings of length 1
    for (let i = 1; i < n; ++i) {
        if (s[i] !== s[i - 1]) {
            count += i; // extend all alternating substrings ending at i-1
        }
    }
    return count;
}

const readline = require('readline').createInterface({
    input: process.stdin,
    output: process.stdout
});

readline.question('', s => {
    const result = alternatingSubstrings(s);
    console.log(result);
    readline.close();
});

#include <iostream>
#include <string>

long long alternatingSubstrings(const std::string& s) {
    long long n = s.length();
    long long count = n; // substrings of length 1
    for (int i = 1; i < n; ++i) {
        if (s[i] != s[i - 1]) {
            count += i; // extend all alternating substrings ending at i-1
        }
    }
    return count;
}

int main() {
    std::string s;
    std::cin >> s;
    long long result = alternatingSubstrings(s);
    std::cout << result << std::endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static long alternatingSubstrings(String s) {
        int n = s.length();
        long count = n; // substrings of length 1
        for (int i = 1; i < n; ++i) {
            if (s.charAt(i) != s.charAt(i - 1)) {
                count += i; // extend all alternating substrings ending at i-1
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        long result = alternatingSubstrings(s);
        System.out.println(result);
    }
}

def alternating_substrings(s):
    n = len(s)
    count = n  # substrings of length 1
    for i in range(1, n):
        if s[i] != s[i - 1]:
            count += i  # extend all alternating substrings ending at i-1
    return count

if __name__ == '__main__':
    s = input()
    result = alternating_substrings(s)
    print(result)

function alternatingSubstrings(s) {
    const n = s.length;
    let count = n; // substrings of length 1
    for (let i = 1; i < n; ++i) {
        if (s[i] !== s[i - 1]) {
            count += i; // extend all alternating substrings ending at i-1
        }
    }
    return count;
}

const readline = require('readline').createInterface({
    input: process.stdin,
    output: process.stdout
});

readline.question('', s => {
    const result = alternatingSubstrings(s);
    console.log(result);
    readline.close();
});

Asked in Top Tech Interviews

Salesforce

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.