Galactic Transmission Protocol — Problem Statement & Solution Guide
Problem Description
You are given a string S consisting solely of the characters 'A', 'B', and 'C'. A substring of S is called *valid* if its length is a multiple of three and every consecutive block of three characters in the substring matches exactly one of the three base cycles: "ABC", "BCA", or "CAB". Your task is to determine how many substrings of S are valid.
Input format:
- A single line containing the string S.
Output format:
- A single integer: the number of valid substrings of S.
The string length can be up to 10^5, so an efficient algorithm is required.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Galactic Transmission Protocol"
WHY DOES IT MATTER?
This problem exemplifies the 'valid substring with cyclic constraints' pattern, which is common in protocol validation, data integrity checks, and sequence matching. It tests the ability to transform a seemingly complex substring counting problem into a linear-time dynamic programming or two-pointer solution by recognizing local transition constraints.
OPTIMIZATION CHALLENGE
The key insight is to avoid checking all substrings by leveraging the fact that validity is a local property (consecutive pairs) and a global property (length multiple of 3). By computing the longest valid suffix ending at each position, we can count valid substrings in O(1) per position, leading to O(N) total time.
REAL-WORLD CONNECTION
In distributed systems, message protocols often require sequences of packets to follow a specific cyclic order (e.g., handshake sequences). Validating that a stream of packets adheres to such a protocol without storing the entire stream is analogous to this problem. It is also relevant in DNA sequence analysis where certain motifs must appear in cyclic patterns.
In interviews, clearly articulate the transition rules first. Draw the state machine for the cycles. Then, explain how to use dynamic programming to compute the longest valid suffix. Emphasize that the count of valid substrings ending at i is simply floor(dp[i] / 3), which is a crucial simplification.
COMPLEXITY AT A GLANCE
O(N)O(1)Core Theory — Why This Approach?
The problem reduces to identifying contiguous segments in the string where the character sequence follows a strict cyclic pattern derived from the set {"ABC", "BCA", "CAB"}. A naive approach would iterate over all O(N^2) substrings and verify each in O(L) time, leading to O(N^3) complexity, which is infeasible for large N. The key insight is that for a substring to be valid, it must be composed of consecutive blocks of length 3, each matching one of the three valid cycles. This implies that the entire substring must adhere to a global cyclic structure. Specifically, if we fix the starting index, the valid characters at subsequent positions are determined by the previous character. For example, if S[i] is 'A', the next valid character in a cycle must be 'B' (for ABC) or 'C' (for CAB). However, since the cycles are rotations of each other, the constraint is that S[i+1] must be the next character in the cycle starting with S[i]. More precisely, the sequence must follow the pattern where S[j] is determined by S[j-1] such that (S[j-1], S[j]) is a valid transition in the cycle graph A->B->C->A. Thus, a valid substring of length 3k is one where every consecutive pair (S[i], S[i+1]) satisfies the transition rule, and the total length is a multiple of 3. This allows us to use a linear scan to compute the maximum valid length starting at each index, then sum the number of valid multiples of 3 within that range.
Interview Questions on This Problem
Q1How would you modify the solution if the valid cycles were "AB", "BC", "CA" instead of length 3, and the substring length had to be a multiple of 2?
The logic remains similar: define valid transitions (A->B, B->C, C->A). For each starting index, extend the substring as long as the next character matches the required transition. Count the number of even-length substrings within the maximum valid length. The time complexity remains O(N) if we precompute the maximum valid length for each start index using a backward pass or dynamic programming.
Q2Can you optimize the space complexity of the solution to O(1) beyond the input string?
Yes. Instead of storing an array of maximum valid lengths, we can compute the count on the fly. For each starting index i, we can extend j as far as possible while the transition holds. However, this is O(N^2) in worst case. To achieve O(N) time and O(1) space, we can use a sliding window or two-pointer technique. Maintain a window [l, r] where the substring S[l..r] is valid. For each r, extend l as needed. But since validity depends on the entire sequence, a better approach is to compute the length of the longest valid suffix ending at each position. Let dp[i] be the length of the longest valid substring ending at i. If S[i-1] and S[i] form a valid transition and dp[i-1] >= 2, then dp[i] = dp[i-1] + 1, else dp[i] = 1. Then, for each i, the number of valid substrings ending at i is floor(dp[i] / 3). Sum these values. This uses O(1) extra space.
Q3What if the string contains only 'A' and 'B', and the valid cycles are "AB" and "BA"? How does the solution change?
The transition graph becomes A->B and B->A. The logic is identical: define valid transitions, compute the longest valid suffix ending at each position, and count multiples of the cycle length (2 in this case). The key is to generalize the transition check and the divisor for the length.
Examples
Input
ABCABC
Output
5
Explanation: All substrings of length 3: positions 1-3 ("ABC"), 2-4 ("BCA"), 3-5 ("CAB"), 4-6 ("ABC"). All four are valid. The only substring of length 6 is 1-6 ("ABCABC"), which splits into "ABC" and "ABC", both valid. No other substrings have length divisible by 3. Total valid substrings = 4 + 1 = 5.
Input
ABCCAB
Output
3
Explanation: Length‑3 substrings: 1-3 ("ABC") valid, 2-4 ("BCC") invalid, 3-5 ("CCA") invalid, 4-6 ("CAB") valid. Length‑6 substring: 1-6 ("ABCCAB") splits into "ABC" and "CAB", both valid. Thus 2 + 1 = 3 valid substrings.
Input
CABCAB
Output
5
Explanation: Length‑3 substrings: 1-3 ("CAB"), 2-4 ("ABC"), 3-5 ("BCA"), 4-6 ("CAB") – all valid. Length‑6 substring: 1-6 ("CABCAB") splits into "CAB" and "CAB", both valid. Total = 4 + 1 = 5.
Constraints
- 1 <= |S| <= 100000
- S consists only of the characters 'A', 'B', and 'C'
Optimal Approach & Strategy
Use dynamic programming to compute the length of the longest valid substring ending at each position based on valid character transitions. For each position, add the number of valid multiples of 3 within that length to the total count.
Brute Force Approach
Iterate over all possible starting and ending indices to generate every substring. For each substring, check if its length is a multiple of 3 and if every consecutive block of 3 characters matches one of the valid cycles.
Verified Code Solutions
function solve(S) {
const n = S.length;
let count = 0;
for (let i = 0; i < n; i++) {
for (let len = 3; i + len <= n; len += 3) {
let valid = true;
for (let j = 0; j < len; j += 3) {
const block = S.substring(i + j, i + j + 3);
if (block !== "ABC" && block !== "BCA" && block !== "CAB") {
valid = false;
break;
}
}
if (valid) count++;
}
}
return count;
}
const S = require('fs').readFileSync(0, 'utf8').trim();
console.log(solve(S));#include <iostream>
#include <string>
using namespace std;
int main() {
string S;
cin >> S;
int n = S.size();
long long count = 0;
// Check all substrings of length multiple of 3
for (int i = 0; i < n; i++) {
for (int len = 3; i + len <= n; len += 3) {
bool valid = true;
for (int j = 0; j < len; j += 3) {
string block = S.substr(i + j, 3);
if (block != "ABC" && block != "BCA" && block != "CAB") {
valid = false;
break;
}
}
if (valid) count++;
}
}
cout << count << endl;
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String S = sc.next();
int n = S.length();
long count = 0;
for (int i = 0; i < n; i++) {
for (int len = 3; i + len <= n; len += 3) {
boolean valid = true;
for (int j = 0; j < len; j += 3) {
String block = S.substring(i + j, i + j + 3);
if (!block.equals("ABC") && !block.equals("BCA") && !block.equals("CAB")) {
valid = false;
break;
}
}
if (valid) count++;
}
}
System.out.println(count);
}
}def solve(S):
n = len(S)
count = 0
for i in range(n):
for length in range(3, n - i + 1, 3):
valid = True
for j in range(0, length, 3):
block = S[i + j:i + j + 3]
if block not in ("ABC", "BCA", "CAB"):
valid = False
break
if valid:
count += 1
return count
if __name__ == "__main__":
S = input().strip()
print(solve(S))function solve(S) {
const n = S.length;
let count = 0;
for (let i = 0; i < n; i++) {
for (let len = 3; i + len <= n; len += 3) {
let valid = true;
for (let j = 0; j < len; j += 3) {
const block = S.substring(i + j, i + j + 3);
if (block !== "ABC" && block !== "BCA" && block !== "CAB") {
valid = false;
break;
}
}
if (valid) count++;
}
}
return count;
}
const S = require('fs').readFileSync(0, 'utf8').trim();
console.log(solve(S));Asked in Top Tech Interviews
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.