Parsing Galactic Transmission Sequences — Problem Statement & Solution Guide
Problem Description
Given a string s that contains only the characters ‘A’, ‘B’, ‘C’, ‘a’, ‘b’, and ‘c’, determine whether s forms a correctly nested transmission. An uppercase letter is an opening signal and must be closed by its exact lowercase counterpart (‘A’↔‘a’, ‘B’↔‘b’, ‘C’↔‘c’). The closing signal must correspond to the most recent unmatched opening signal (LIFO order). Return true if every character is matched and the nesting is proper; otherwise return false.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Parsing Galactic Transmission Sequences"
WHY DOES IT MATTER?
Balanced‑symbol validation appears in compilers, interpreters, markup parsers, and protocol designers; mastering the stack pattern ensures you can guarantee structural correctness of nested constructs efficiently.
OPTIMIZATION CHALLENGE
The key insight is that only the most recent unmatched opening can be closed next, allowing a single pass with a push/pop structure instead of repeated scans, collapsing O(n²) work into O(n).
REAL-WORLD CONNECTION
Think of a call stack in a distributed microservice trace: each service call (uppercase) must be paired with its response (lowercase) in reverse order, mirroring how a stack tracks pending operations.
When coding, first write a small helper that maps an opening to its closing; then treat the stack as a simple array with an index pointer to avoid costly push/pop overhead in languages without built‑in stack primitives.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The problem is a classic instance of the balanced‑parentheses family, where each opening token (uppercase A, B, C) must be closed by its exact lowercase counterpart in a strict LIFO order. A naïve solution might scan the string and try to match each closing character by searching backwards for an unmatched opening, leading to O(n²) time on long inputs because each closing could trigger a linear scan. The optimal paradigm leverages a stack: as we iterate left‑to‑right, we push every opening symbol onto the stack and pop when we encounter a matching closing symbol, guaranteeing each character is processed exactly once. This yields linear time and linear‑in‑the‑worst‑case space, which is optimal because any algorithm must inspect each character at least once to verify nesting.
Interview Questions on This Problem
Q1How would you modify the algorithm to support an arbitrary set of matching pairs, such as parentheses, brackets, and braces, in addition to the A/a, B/b, C/c pairs?
Maintain a hash map that maps each opening character to its corresponding closing character (and optionally the reverse). While scanning, push opening chars onto the stack; when a closing char appears, check if the stack is non‑empty and whether the top’s mapped closing matches the current char. This generalizes the solution without changing its O(n) complexity.
Q2What is the worst‑case space usage of the stack for a string of length n, and can you reduce it further?
The worst case occurs when the string consists solely of opening symbols, so the stack holds n elements, i.e., O(n) space. This is asymptotically optimal because any algorithm must remember unmatched openings to validate later closings; you cannot compress that information without losing correctness.
Q3If the input string is streamed (character by character) and you cannot store the entire string, does the stack‑based solution still work?
Yes. The stack only needs to retain currently unmatched openings, which is independent of the total input size. As each character arrives, you push or pop accordingly, making the algorithm suitable for streaming or memory‑constrained environments.
Examples
Input
"ABab"
Output
false
Explanation: Read ‘A’ → push A; ‘B’ → push B; ‘a’ → expects to close the top of the stack (B) but finds ‘a’, which closes A → mismatch → invalid.
Input
"AaBb"
Output
true
Explanation: ‘A’ push; ‘a’ matches top A → pop; stack empty. ‘B’ push; ‘b’ matches top B → pop; stack empty at end → valid.
Input
"ABCcba"
Output
true
Explanation: Push A, B, C. ‘c’ matches C → pop. ‘b’ matches B → pop. ‘a’ matches A → pop. Stack empty → valid.
Constraints
- 1 <= s.length <= 10^5
- s consists only of the characters 'A','B','C','a','b','c'
- The algorithm must run in O(n) time and O(n) auxiliary space in the worst case
Optimal Approach & Strategy
Use a stack: push openings, pop when a matching closing appears, and ensure the stack is empty after processing the whole string.
Brute Force Approach
For each closing character, scan leftwards to find the nearest unmatched opening of the same type, marking it as used; this leads to quadratic time on long strings.
Verified Code Solutions
function isValidTransmission(s) {
const stack = [];
for (const c of s) {
if (c === 'A' || c === 'B' || c === 'C') {
stack.push(c);
} else {
if (stack.length === 0) return false;
const top = stack.pop();
if (c === 'a' && top !== 'A') return false;
if (c === 'b' && top !== 'B') return false;
if (c === 'c' && top !== 'C') return false;
}
}
return stack.length === 0;
}
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
terminal: false
});
rl.on('line', (line) => {
const s = line.trim();
console.log(isValidTransmission(s) ? 'true' : 'false');
rl.close();
});#include <iostream>
#include <string>
#include <stack>
using namespace std;
bool isValidTransmission(const string& s) {
stack<char> st;
for (char c : s) {
if (c == 'A' || c == 'B' || c == 'C') {
st.push(c);
} else {
if (st.empty()) return false;
char top = st.top();
st.pop();
if (c == 'a' && top != 'A') return false;
if (c == 'b' && top != 'B') return false;
if (c == 'c' && top != 'C') return false;
}
}
return st.empty();
}
int main() {
string s;
cin >> s;
cout << (isValidTransmission(s) ? "true" : "false") << endl;
return 0;
}import java.util.Scanner;
import java.util.Stack;
public class Main {
public static boolean isValidTransmission(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == 'A' || c == 'B' || c == 'C') {
stack.push(c);
} else {
if (stack.isEmpty()) return false;
char top = stack.pop();
if (c == 'a' && top != 'A') return false;
if (c == 'b' && top != 'B') return false;
if (c == 'c' && top != 'C') return false;
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.next();
System.out.println(isValidTransmission(s) ? "true" : "false");
scanner.close();
}
}def is_valid_transmission(s: str) -> bool:
stack = []
for c in s:
if c in 'ABC':
stack.append(c)
else:
if not stack:
return False
top = stack.pop()
if c == 'a' and top != 'A':
return False
if c == 'b' and top != 'B':
return False
if c == 'c' and top != 'C':
return False
return len(stack) == 0
if __name__ == "__main__":
s = input().strip()
print("true" if is_valid_transmission(s) else "false")function isValidTransmission(s) {
const stack = [];
for (const c of s) {
if (c === 'A' || c === 'B' || c === 'C') {
stack.push(c);
} else {
if (stack.length === 0) return false;
const top = stack.pop();
if (c === 'a' && top !== 'A') return false;
if (c === 'b' && top !== 'B') return false;
if (c === 'c' && top !== 'C') return false;
}
}
return stack.length === 0;
}
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
terminal: false
});
rl.on('line', (line) => {
const s = line.trim();
console.log(isValidTransmission(s) ? 'true' : 'false');
rl.close();
});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.