Alternate Ingredient 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 Alternate Ingredient Sequence Length problem optimally.

TopicStrings

PatternMixed

TimeO(n)

SpaceO(1)

Problem Description

Given a string categories composed of uppercase English letters, determine the maximum possible length of a subsequence that alternates strictly between the characters ‘A’ and ‘B’. While forming the subsequence, any character other than ‘A’ or ‘B’ must be ignored and cannot appear in the subsequence. The subsequence does not need to be contiguous; you may skip any number of characters. Return the length of the longest such alternating subsequence. If the string contains no ‘A’ or ‘B’, the answer is 0.

DSA Pattern Breakdown

"Alternate Ingredient Sequence Length"

medium

WHY DOES IT MATTER?

Alternating‑pattern detection appears in protocol state machines, error‑correction codes, and UI event streams where two states must flip consistently; mastering this pattern sharpens a candidate’s ability to model sequential constraints efficiently.

OPTIMIZATION CHALLENGE

The key insight is that only the most recent character matters for future extensions, allowing us to collapse the DP table to two scalar variables instead of an O(n) array, thus achieving linear time and constant space.

REAL-WORLD CONNECTION

Think of a distributed lock that must be handed off strictly between two services (A and B). The longest safe hand‑off sequence corresponds to the longest alternating subsequence, and the O(1) state machine mirrors the lock’s token‑passing logic.

During the interview, write the two‑variable update clearly, handle the ‘ignore‑other‑chars’ case by simply skipping them, and remember to return the max of the two counters at the end.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem asks for the longest subsequence that strictly alternates between the two characters ‘A’ and ‘B’, discarding any other letters. A naïve solution would examine every possible subsequence, leading to exponential time, or use an O(n^2) DP that checks each pair of positions, which quickly becomes infeasible for strings of length up to 10^5. The optimal paradigm treats the task as a linear‑time state machine: maintain two counters – one for the longest alternating subsequence ending with ‘A’ and one for the longest ending with ‘B’. As we scan the string, each ‘A’ can extend a sequence that previously ended with ‘B’, and each ‘B’ can extend a sequence that previously ended with ‘A’. This greedy update yields the maximum possible length in a single pass because any optimal subsequence must respect the same local alternation property, making the global optimum achievable by locally optimal choices.

Interview Questions on This Problem

Q1How would you modify the solution if the required alternating characters were any two distinct letters supplied at runtime?

Treat the two target letters as variables X and Y, keep two counters for sequences ending with X and Y, and update them exactly as with ‘A’ and ‘B’; the algorithm remains O(n) and O(1) space.

Q2Can you compute the number of distinct longest alternating subsequences, not just the length?

Yes – augment each counter with a count of ways to achieve that length, updating counts when lengths increase or tie, taking care to use modulo arithmetic for large numbers; this still runs in O(n) time and O(1) extra space.

Q3Why does a simple two‑pointer sliding window not work for this problem?

A sliding window assumes contiguity, but the subsequence can skip characters; the optimal solution depends only on the order of ‘A’ and ‘B’, not on a contiguous block, so a window would miss valid skips and give incorrect lengths.

Examples

Example 1

Input

"ABAB"

Output

Explanation: All characters are either ‘A’ or ‘B’ and already alternate: A‑B‑A‑B. The whole string forms a valid subsequence, so the maximum length is 4.

Example 2

Input

"AAXBBAB"

Output

Explanation: Removing non‑‘A’/‘B’ characters yields A A B B A B. The longest alternating subsequence is A‑B‑A‑B (choose positions 0,2,4,5), giving length 4.

Example 3

Input

"BAABABAA"

Output

Explanation: Filtering to A/B gives B A A B A B A A. One optimal subsequence is B‑A‑B‑A‑B‑A (positions 0,1,3,4,5,6), which alternates perfectly and has length 6.

Constraints

1 <= categories.length <= 200000
categories consists only of uppercase English letters ('A'‑'Z')
Only the characters 'A' and 'B' are relevant for the subsequence; all others are ignored
The required algorithm should run in O(n) time and O(1) additional space

Optimal Approach & Strategy

Maintain two counters for sequences ending with A and B, update them in a single left‑to‑right pass, and return the max – linear time, constant space.

Brute Force Approach

Generate every subsequence, filter those containing only A and B, check if they strictly alternate, and keep the longest – exponential time.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

function alternateIngredientSequenceLength(categories) {
    let count = 0;
    let expected = 'A'; // Start expecting 'A'
    
    for (let i = 0; i < categories.length; i++) {
        if (categories[i] === expected) {
            count++;
            // Toggle expected character
            expected = (expected === 'A') ? 'B' : 'A';
        }
    }
    
    return count;
}

// Driver code
const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

rl.question('', (input) => {
    const result = alternateIngredientSequenceLength(input.trim());
    console.log(result);
    rl.close();
});

#include <iostream>
#include <string>

using namespace std;

int alternateIngredientSequenceLength(const string& categories) {
    int count = 0;
    char expected = 'A'; // Start expecting 'A'
    
    for (char c : categories) {
        if (c == expected) {
            count++;
            // Toggle expected character
            expected = (expected == 'A') ? 'B' : 'A';
        }
    }
    
    return count;
}

int main() {
    string input;
    cin >> input;
    cout << alternateIngredientSequenceLength(input) << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static int alternateIngredientSequenceLength(String categories) {
        int count = 0;
        char expected = 'A'; // Start expecting 'A'
        
        for (int i = 0; i < categories.length(); i++) {
            if (categories.charAt(i) == expected) {
                count++;
                // Toggle expected character
                expected = (expected == 'A') ? 'B' : 'A';
            }
        }
        
        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine().trim();
        System.out.println(alternateIngredientSequenceLength(input));
        scanner.close();
    }
}

def alternate_ingredient_sequence_length(categories: str) -> int:
    count = 0
    expected = 'A'  # Start expecting 'A'
    
    for c in categories:
        if c == expected:
            count += 1
            # Toggle expected character
            expected = 'B' if expected == 'A' else 'A'
    
    return count

if __name__ == "__main__":
    categories = input().strip()
    print(alternate_ingredient_sequence_length(categories))

function alternateIngredientSequenceLength(categories) {
    let count = 0;
    let expected = 'A'; // Start expecting 'A'
    
    for (let i = 0; i < categories.length; i++) {
        if (categories[i] === expected) {
            count++;
            // Toggle expected character
            expected = (expected === 'A') ? 'B' : 'A';
        }
    }
    
    return count;
}

// Driver code
const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

rl.question('', (input) => {
    const result = alternateIngredientSequenceLength(input.trim());
    console.log(result);
    rl.close();
});

Asked in Top Tech Interviews

InfosysMicrosoft

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.