Alternating Signal Sequences ā Problem Statement & Solution Guide
Problem Description
Given a string of signals consisting of 'A', 'B', and 'C', find the length of the longest substring where the signals appear in an alternating sequence of 3 distinct signal types, with each signal type appearing only once in the sequence and the sequence starting and ending with either 'A' or 'C'.
Examples
Input
ACBACB
Output
5
Explanation: Step-by-step: with input ACBACB, we start with 'A', then 'C', then 'B', then 'A', then 'C', then 'B', giving output 5
Input
ABCBA
Output
4
Explanation: Step-by-step: with input ABCBA, we start with 'A', then 'B', then 'C', then 'B', then 'A', giving output 4
Constraints
- The input string will only contain the characters 'A', 'B', and 'C'.
- The length of the input string will not exceed 1000 characters.
Optimal Approach & Strategy
The optimal approach uses a sliding window technique to efficiently scan the input string, keeping track of the maximum length of the valid alternating sequence found so far. This approach has a time complexity of O(n) and can be implemented using a single loop to iterate over the input string.
Brute Force Approach
The brute-force approach involves checking every possible substring of the input string to see if it meets the pattern requirements, resulting in a time complexity of O(nĀ²). This approach is inefficient and not scalable for large inputs. It can be implemented using nested loops to generate all substrings and a separate function to check if each substring is valid.
Verified Code Solutions
function longestAlternatingSequence(str) {
let maxLen = 0;
let currLen = 0;
let set = new Set();
let startChar = null;
for (let i = 0; i < str.length; i++) {
if (set.size === 3) {
if (str[i] === str[i - 1] || set.has(str[i])) {
set.clear();
currLen = 0;
startChar = null;
}
}
if (startChar === null) {
startChar = str[i];
}
if (str[i] !== startChar) {
set.add(str[i]);
currLen++;
maxLen = Math.max(maxLen, currLen);
}
}
return maxLen;
}class Solution {
public int longestAlternatingSequence(String s) {
int max_length = 0;
for (int i = 0; i < s.length(); i++) {
for (int j = i + 1; j < s.length(); j++) {
for (int k = j + 1; k < s.length(); k++) {
String sequence = s.substring(i, i + 1) + s.substring(j, j + 1) + s.substring(k, k + 1);
if (sequence.length() == 3 && sequence.charAt(0) != sequence.charAt(2) && sequence.charAt(0) != sequence.charAt(1) && sequence.charAt(1) != sequence.charAt(2)) {
max_length = Math.max(max_length, sequence.length());
}
}
}
}
return max_length;
}
}def longestAlternatingSequence(s):
max_length = 0
for i in range(len(s)):
for j in range(i + 1, len(s)):
for k in range(j + 1, len(s)):
sequence = s[i] + s[j] + s[k]
if len(set(sequence)) == 3 and sequence[0] != sequence[2] and sequence[0] != sequence[1] and sequence[1] != sequence[2]:
max_length = max(max_length, len(sequence))
return max_lengthfunction longestAlternatingSequence(str) {
let maxLen = 0;
let currLen = 0;
let set = new Set();
let startChar = null;
for (let i = 0; i < str.length; i++) {
if (set.size === 3) {
if (str[i] === str[i - 1] || set.has(str[i])) {
set.clear();
currLen = 0;
startChar = null;
}
}
if (startChar === null) {
startChar = str[i];
}
if (str[i] !== startChar) {
set.add(str[i]);
currLen++;
maxLen = Math.max(maxLen, currLen);
}
}
return maxLen;
}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.