Galactic Morse Encoder — Problem Statement & Solution Guide
Problem Description
In a deep-space communication protocol, signals are encoded using a binary-like alphabet consisting of two symbols: 'X' representing a short pulse (dot) and 'Y' representing a long pulse (dash). A transmission segment is considered valid if and only if it is composed exclusively of 'X' and 'Y' characters, and no two consecutive characters within the segment are identical. This alternating pattern ensures maximum signal clarity and prevents receiver ambiguity.
Given a string s of length n, determine the maximum length of any contiguous substring that satisfies the validity conditions. If the string contains no valid segment (i.e., no 'X' or 'Y' characters, or no alternating pair exists), return 0.
Input: A single string s consisting of uppercase English letters.
Output: An integer representing the length of the longest valid Morse-like segment.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Galactic Morse Encoder"
WHY DOES IT MATTER?
This pattern is essential for understanding state-dependent string processing. It teaches candidates how to handle constraints that depend on the immediate history (previous character) rather than global properties. It is a fundamental building block for more complex problems involving pattern matching, sequence validation, and state machines.
OPTIMIZATION CHALLENGE
The key insight is recognizing that the validity of a substring depends only on the last character of the previous valid segment. This allows for a single-pass solution without backtracking or complex data structures. The challenge is to correctly handle the reset condition when a violation occurs.
REAL-WORLD CONNECTION
This is analogous to validating data integrity in communication protocols (like Morse code, binary streams, or parity checks) where alternating patterns ensure signal distinguishability. It is also similar to detecting anomalies in time-series data where values must oscillate within a specific range.
In interviews, explicitly state that you are using a 'state machine' or 'sliding window' approach. Clarify that you are tracking the 'previous character' as state. Avoid using regex for this problem as it is less efficient and harder to explain the O(n) complexity clearly.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The 'Galactic Morse Encoder' problem is fundamentally a constraint satisfaction and pattern recognition task within string processing. The core requirement is that the string must consist exclusively of 'X' and 'Y' and must alternate strictly (no two adjacent characters can be the same). This implies that for any valid segment of length $n$, the string is entirely determined by its first character. If the first character is 'X', the string must be $X, Y, X, Y, \dots$; if it is 'Y', it must be $Y, X, Y, X, \dots$. Therefore, there are at most two valid patterns for any given length. The algorithmic challenge lies in efficiently validating a given string against these two possible alternating patterns or generating/counting valid segments within a larger, potentially invalid, input stream.
Naive approaches that attempt to generate all possible binary strings of length $n$ and filter them fail catastrophically due to exponential time complexity $O(2^n)$. Even a simple linear scan that checks every adjacent pair $s[i] == s[i+1]$ is optimal for validation ($O(n)$), but if the problem involves finding the longest valid substring or counting valid segments in a noisy signal, a sliding window or state-machine approach is required. The key theoretical insight is that the 'alternating' constraint creates a rigid structure: once a violation (two identical consecutive characters) is found, the current valid segment ends, and a new segment must start at the next character. This transforms the problem from a global search into a local state tracking problem.
The optimal paradigm is a single-pass linear scan using a state variable (or simply tracking the previous character). For validation, we iterate through the string, ensuring each character is either 'X' or 'Y' and differs from the previous one. For more complex variations (like finding the longest valid substring), we maintain a start index for the current valid window. When a violation occurs at index $i$ (where $s[i] == s[i-1]$ or invalid char), we update the maximum length and reset the start index to $i$. This ensures $O(n)$ time complexity and $O(1)$ space complexity, which is optimal for string problems of this nature.
Interview Questions on This Problem
Q1At a fintech platform, we need to validate transaction IDs that must alternate between 'A' and 'B'. How would you design a validator that handles millions of IDs per second with minimal memory overhead?
I would implement a linear scan validator that checks two conditions in a single pass: 1) The character is either 'A' or 'B', and 2) It is not equal to the previous character. This runs in O(n) time and O(1) space. For high throughput, I would avoid creating new string objects or using regex, instead using direct character comparison in a tight loop. If the IDs are fixed-length, I can unroll the loop for further optimization.
Q2In a distributed system, we receive fragmented log entries that should form an alternating pattern. How do you find the longest contiguous valid segment in a stream of characters?
I would use a sliding window approach. Maintain a start pointer for the beginning of the current valid segment and a current pointer for the end. Iterate through the stream, and if the current character is invalid or matches the previous one, update the maximum length found so far and reset start to the current index. This ensures we process each character exactly once, resulting in O(n) time and O(1) space complexity.
Q3How would you modify the algorithm to count the number of valid substrings in a string of length $n$ where valid means alternating 'X' and 'Y'?
I would iterate through the string, keeping track of the length of the current valid alternating suffix ending at index $i$. If $s[i] != s[i-1]$, the current valid suffix length increases by 1. If $s[i] == s[i-1]$, the current valid suffix length resets to 1. The total count is the sum of these suffix lengths. This works because any valid substring ending at $i$ must be a suffix of the longest valid alternating sequence ending at $i$. This runs in O(n) time and O(1) space.
Examples
Input
s = "AXYXYB"
Output
4
Explanation: Scan the string for contiguous segments containing only 'X' and 'Y'. The substring "XYXY" (indices 1 to 4) consists solely of 'X' and 'Y' and alternates perfectly: X≠Y, Y≠X, X≠Y. Its length is 4. The character 'A' at index 0 and 'B' at index 5 break any potential extension. No longer valid segment exists. Return 4.
Input
s = "XXYY"
Output
2
Explanation: The string contains only 'X' and 'Y'. However, the first two characters are 'X' and 'X' (identical), breaking the alternation rule. The segment "XX" is invalid. The next pair "YY" is also invalid. The longest valid contiguous segment is a single character, either "X" or "Y", which trivially satisfies the condition (no adjacent pairs to violate). Maximum length is 1.
Input
s = "HELLO"
Output
0
Explanation: The string contains no 'X' or 'Y' characters. Therefore, no valid segment can be formed. Return 0.
Input
s = "YXYYX"
Output
3
Explanation: Identify contiguous regions of 'X' and 'Y'. The entire string is composed of 'X' and 'Y'. Check alternation: Y≠X (valid), X≠Y (valid), Y≠Y (invalid). The segment "YX" (indices 0-1) is valid with length 2. The segment "XY" (indices 1-2) is valid with length 2. The segment "YY" (indices 2-3) is invalid. The segment "YX" (indices 3-4) is valid with length 2. The maximum length among all valid segments is 2.
Constraints
- 1 <= s.length <= 10^5
- s consists of uppercase English letters only
- Time complexity must be O(n) where n is the length of the string
- Space complexity must be O(1)
Optimal Approach & Strategy
Iterate through the string once, comparing each character to the previous one. If the current character is not 'X' or 'Y', or if it is the same as the previous character, the string is invalid (or the current valid segment ends). This single-pass approach runs in O(n) time and O(1) space.
Brute Force Approach
Generate all possible strings of length n using 'X' and 'Y', and for each string, check if it satisfies the alternating constraint. This approach has exponential time complexity O(2^n) and is infeasible for large n.
Verified Code Solutions
function longestValidSegment(s) {
const n = s.length;
if (n === 0) return 0;
let maxLen = 0;
let currentLen = 0;
let prev = '';
for (let i = 0; i < n; i++) {
const c = s[i];
if (c === 'X' || c === 'Y') {
if (currentLen === 0 || c !== prev) {
currentLen++;
prev = c;
} else {
currentLen = 1;
prev = c;
}
} else {
currentLen = 0;
prev = '';
}
maxLen = Math.max(maxLen, currentLen);
}
return maxLen;
}
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim();
console.log(longestValidSegment(input));#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int longestValidSegment(string s) {
int n = s.size();
if (n == 0) return 0;
int maxLen = 0;
int currentLen = 0;
char prev = 0;
for (int i = 0; i < n; i++) {
char c = s[i];
if (c == 'X' || c == 'Y') {
if (currentLen == 0 || c != prev) {
currentLen++;
prev = c;
} else {
currentLen = 1;
prev = c;
}
} else {
currentLen = 0;
prev = 0;
}
maxLen = max(maxLen, currentLen);
}
return maxLen;
}
int main() {
string s;
cin >> s;
cout << longestValidSegment(s) << endl;
return 0;
}import java.util.Scanner;
public class Main {
public static int longestValidSegment(String s) {
int n = s.length();
if (n == 0) return 0;
int maxLen = 0;
int currentLen = 0;
char prev = 0;
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (c == 'X' || c == 'Y') {
if (currentLen == 0 || c != prev) {
currentLen++;
prev = c;
} else {
currentLen = 1;
prev = c;
}
} else {
currentLen = 0;
prev = 0;
}
maxLen = Math.max(maxLen, currentLen);
}
return maxLen;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.next();
System.out.println(longestValidSegment(s));
scanner.close();
}
}def longest_valid_segment(s: str) -> int:
n = len(s)
if n == 0:
return 0
max_len = 0
current_len = 0
prev = ''
for c in s:
if c in ('X', 'Y'):
if current_len == 0 or c != prev:
current_len += 1
prev = c
else:
current_len = 1
prev = c
else:
current_len = 0
prev = ''
max_len = max(max_len, current_len)
return max_len
if __name__ == "__main__":
s = input().strip()
print(longest_valid_segment(s))function longestValidSegment(s) {
const n = s.length;
if (n === 0) return 0;
let maxLen = 0;
let currentLen = 0;
let prev = '';
for (let i = 0; i < n; i++) {
const c = s[i];
if (c === 'X' || c === 'Y') {
if (currentLen === 0 || c !== prev) {
currentLen++;
prev = c;
} else {
currentLen = 1;
prev = c;
}
} else {
currentLen = 0;
prev = '';
}
maxLen = Math.max(maxLen, currentLen);
}
return maxLen;
}
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim();
console.log(longestValidSegment(input));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.