Alternating Sequence Length — Problem Statement & Solution Guide

StringsMediumMixed

TimeO(n)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Strings and solve the Alternating Sequence Length 2 problem optimally.

TopicStrings

PatternMixed

TimeO(n)

SpaceO(1)

Problem Description

Given a string S containing only the characters 'A' and 'B', determine the greatest possible length of a subsequence (not necessarily contiguous) that alternates strictly between the two characters. The subsequence may begin with either 'A' or 'B' and must follow the pattern ABAB… or BABA…. If no alternating subsequence of length at least two exists, output 0.

DSA Pattern Breakdown

"Alternating Sequence Length"

medium

WHY DOES IT MATTER?

Alternating patterns appear in signal processing, error‑checking codes, and load‑balancing where resources must switch states predictably; mastering this pattern sharpens a candidate's ability to reason about state transitions in linear time.

OPTIMIZATION CHALLENGE

The key insight is that only the last character of a candidate subsequence matters, allowing us to collapse the DP state to two scalar variables instead of an O(n) table.

REAL-WORLD CONNECTION

Think of a distributed system that alternates between primary and backup nodes for health checks; the longest feasible alternating schedule corresponds to the longest subsequence you can schedule without violating the primary‑backup order.

During the interview, write the two‑variable update on the whiteboard first, then walk through a short example to prove correctness before coding.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem asks for the longest alternating subsequence of a binary string composed of 'A' and 'B'. A subsequence can skip characters, so the optimal solution depends only on the relative order of the two symbols, not on contiguity. A naive solution would enumerate all 2^n subsets and test each for alternation, which is infeasible for n>30. The optimal paradigm is a linear‑time greedy scan: we keep two counters, one for a subsequence ending with 'A' and one ending with 'B'. When we see an 'A', we can extend any subsequence that previously ended with 'B' (counterB+1) and similarly for 'B'. The answer is the maximum of the two counters, but we must ensure the length is at least 2; otherwise we return 0. This dynamic‑programming‑in‑O(1)‑space approach reduces the exponential blow‑up to O(n) time and O(1) extra space.

Interview Questions on This Problem

Q1How would you compute the longest alternating subsequence in a string of 'A' and 'B' in O(n) time?

Maintain two variables, endA and endB. Iterate the string; when you encounter 'A', set endA = endB + 1; when you encounter 'B', set endB = endA + 1. The answer is max(endA,endB) if it is ≥2, else 0.

Q2Why does a simple count of the number of 'A's and 'B's not give the correct answer?

Because the alternating constraint forces the order to alternate; excess of one character that appears consecutively cannot be used unless interleaved with the opposite character, so the raw counts ignore positional information.

Q3Can you adapt the solution to handle three characters, say 'A','B','C', where the subsequence must strictly cycle A→B→C→A…?

Yes. Keep three counters, each representing the longest subsequence ending with a particular character, and update each counter based on the predecessor in the cycle (e.g., when seeing 'B', set cntB = cntA + 1). The same O(n) scan works with O(k) space for k characters.

Examples

Example 1

Input

ABABAB

Output

Explanation: The whole string already follows an AB pattern, so the longest alternating subsequence includes all six characters.

Example 2

Input

AAABBB

Output

Explanation: Select the first 'A' (position 0) and the first 'B' (position 3). After a 'B' there is no later 'A', so the longest alternating subsequence has length 2.

Example 3

Input

BABAAB

Output

Explanation: Choose characters at positions 0(B),1(A),2(B),3(A),5(B). This yields the subsequence B A B A B, which alternates and has length 5; no longer alternating subsequence exists.

Constraints

1 <= |S| <= 200000
S consists only of characters 'A' and 'B'
Time limit: 1 second
Memory limit: 256 MB

Optimal Approach & Strategy

Use two counters updated in a single pass: endA = endB+1 on 'A', endB = endA+1 on 'B'. The result is max(endA,endB) with a minimum of 2.

Brute Force Approach

Enumerate every subset of indices, build the corresponding subsequence, and check if it alternates; keep the longest valid length. This runs in exponential time O(2^n).

Code Solutions

Language:

JavaScript Solution

Time: O(n)

const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim();
function longestAlternating(s){
    let cntA=0, cntB=0;
    for(const ch of s){
        if(ch==='A') cntA++;
        else if(ch==='B') cntB++;
    }
    if(cntA===0 || cntB===0) return 0;
    if(cntA===cntB) return cntA+cntB;
    return 2*Math.min(cntA,cntB)+1;
}
console.log(longestAlternating(input));

#include <bits/stdc++.h>
using namespace std;
int longestAlternating(const string& s){
    long long cntA=0,cntB=0;
    for(char c: s){
        if(c=='A') ++cntA;
        else if(c=='B') ++cntB;
    }
    if(cntA==0 || cntB==0) return 0;
    if(cntA==cntB) return cntA+cntB;
    return (int)(2*min(cntA,cntB)+1);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s; if(!(cin>>s)) return 0;
    cout<<longestAlternating(s);
    return 0;
}

import java.io.*;
public class Main {
    static int longestAlternating(String s){
        long cntA=0, cntB=0;
        for(int i=0;i<s.length();i++){
            char c=s.charAt(i);
            if(c=='A') cntA++;
            else if(c=='B') cntB++;
        }
        if(cntA==0 || cntB==0) return 0;
        if(cntA==cntB) return (int)(cntA+cntB);
        return (int)(2*Math.min(cntA,cntB)+1);
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        if(s==null) s="";
        System.out.print(longestAlternating(s));
    }
}

import sys
def longest_alternating(s):
    cntA = s.count('A')
    cntB = s.count('B')
    if cntA==0 or cntB==0:
        return 0
    if cntA==cntB:
        return cntA+cntB
    return 2*min(cntA,cntB)+1
if __name__=="__main__":
    s = sys.stdin.read().strip()
    print(longest_alternating(s))

const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim();
function longestAlternating(s){
    let cntA=0, cntB=0;
    for(const ch of s){
        if(ch==='A') cntA++;
        else if(ch==='B') cntB++;
    }
    if(cntA===0 || cntB===0) return 0;
    if(cntA===cntB) return cntA+cntB;
    return 2*Math.min(cntA,cntB)+1;
}
console.log(longestAlternating(input));

Asked in Top Tech Interviews

AdobeAccenture

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.