Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Delete every character except two chosen distinct letters, and the survivor must alternate (no two adjacent equal) — find the longest such string. For each unordered pair of distinct letters present in s, keep only those two letters and check the filtered string alternates; if it does, its length is a candidate. Return the max candidate, or 0 if none qualifies. With alphabet size k ≤ 26, that's O(k² · n) — for lowercase letters, effectively O(n).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you exploit the 'exactly two distinct letters' constraint to bound the search to letter pairs instead of all subsequences, and whether you correctly define 'valid' as strict alternation after filtering.
Where candidates slip
Trying to build the answer greedily in one pass, or forgetting that a pair which produces adjacent duplicates (like 'aa') after filtering must be rejected entirely — not just trimmed.
How to stand out
Point out the alphabet bound: there are at most C(26,2)=325 pairs, so enumerating pairs and filtering is O(k²·n), and that 'valid' reduces to a single adjacency scan per pair.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewString sAlternates?NoYesExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Generate All Subsequences (Brute Force)
1Hint 1Explore hintHide hint
The naive reading is 'choose any subset of positions to keep'. How many subsets are there?
2Hint 2Explore hintHide hint
Enumerate all 2ⁿ subsequences; for each, check it has exactly two distinct chars and alternates.
3Hint 3Explore hintHide hint
This explodes immediately — note it only to motivate exploiting the two-letter constraint.
A · Core idea
The most literal interpretation: a valid string is some subsequence of s, so enumerate every subsequence and test the two conditions (exactly two distinct letters, strictly alternating), tracking the longest valid one.
Why it's correct. It examines every possible deletion outcome, so it cannot miss the optimum.
Why it's unusable. With n up to 1000 there are 2¹⁰⁰⁰ subsequences — astronomically more than atoms in the universe. The point of stating it is to surface the key realization: the answer is constrained to two distinct letters, and once you fix which two, the best subsequence is forced (keep both letters, drop the rest). That collapses 2ⁿ choices into one per letter pair.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = "abc"Array state
keep 0,1
"ab" → valid
2C · Code with teaching comments
Reference implementation previewpublic int twoCharacters(String s) { int n = s.length(); int best = 0; for (int mask = 1; mask < (1 << n); mask++) { StringBuilder sb = new StringBuilder();Explore the full codeHide the full code
D · Why it works and complexityO(2ⁿ · n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
When a brute force is exponential but the answer is restricted to a tiny structure (here: two letters), enumerate the structure, not the raw choices. Fixing the two letters removes all freedom — you must keep every occurrence of both — so there's nothing left to search inside a pair.
ComplexityO(2ⁿ · n) time, O(n) space — There are 2ⁿ subsequences, and validating each costs O(n) → O(2ⁿ · n). Hopeless beyond n ≈ 20.
E · Edge cases and pitfalls5s = "a" — No subsequence has two distinct letters → 0.Explore edge casesHide edge cases
Edge cases handled
s = "a"No subsequence has two distinct letters → 0.s = "ab""ab" is valid → 2.
Pitfalls
- Believing this can run for n = 1000 — it cannot.
- Forgetting the exactly-two-distinct check and counting single-letter strings.
- Not realizing fixing two letters removes all internal choice.
Approach 2 of 2 · Optimal
Enumerate Letter Pairs and Filter (Optimal)
1Hint 1Explore hintHide hint
The result uses exactly two distinct letters. How many such pairs are possible over a 26-letter alphabet?
2Hint 2Explore hintHide hint
For each pair of distinct letters present in s, remove every other letter — the survivors are forced.
3Hint 3Explore hintHide hint
If the filtered string has any two equal adjacent characters it's invalid; otherwise its length is a candidate. Take the max.
A · Core idea
Collect the distinct letters of s. For every unordered pair {x, y}, build the filtered string keeping only x and y in their original order. The filtered string is valid iff no two adjacent characters are equal; if valid, its length is a candidate. Return the largest candidate, or 0.
Why fixing the pair removes all choice. Once you commit to letters x and y, deleting is mandatory for every other letter and forbidden for x/y (deleting an occurrence could only shorten or break alternation, never help). So the unique best subsequence for that pair is the full filtered string — there's nothing to optimize within a pair.
Why the alternation check is a simple adjacency scan. After filtering, the only failure mode is two of the same letter sitting next to each other (which happens when the original had …x x… with nothing of y between them). Scanning neighbours catches exactly that. If it survives, the string already alternates x y x y ….
Why reject, not trim. If "aabab" filters to "aabab" with a leading aa, you can't just drop one a — you committed to keeping all of x and y. So a duplicate adjacency disqualifies the whole pair; you don't salvage a prefix.
Why the alphabet bound makes this fast. At most 325 pairs, each costing O(n), is trivially within limits for n ≤ 1000.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = "beabeefeab"Array state
keep {a,b}
drop e,f → "babab"
5C · Code with teaching comments
D · Why it works and complexityO(k² · n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
The 'exactly two letters' rule is a search-space cap in disguise: instead of choosing among 2ⁿ subsequences, you choose among ≤ 325 letter pairs, and each pair has a single forced answer. Spotting a small fixed alphabet and turning it into the outer loop is the reusable trick.
ComplexityO(k² · n) time, O(n) space — There are at most C(k,2) ≤ 325 letter pairs. Filtering and the alternation check are each O(n). Total O(k² · n); for lowercase letters k ≤ 26 so this is effectively linear in n with a constant factor.
E · Edge cases and pitfalls6s = "aaa" — Only one distinct letter → no pair exists → 0.Explore edge casesHide edge cases
Edge cases handled
s = "aaa"Only one distinct letter → no pair exists → 0.s = "abab"Pair {a,b} filters to "abab", alternates → 4.s = "abba"Pair {a,b} → "abba" has 'bb' → reject → 0.
Pitfalls
- Trimming a bad filtered string instead of rejecting the pair entirely.
- Counting filtered strings of length 1 (only one distinct letter) as valid.
- Pairing letters that don't occur in s — harmless but wasted work; iterate present letters only.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int twoCharacters(String s) { java.util.List<Character> distinct = new java.util.ArrayList<>( new java.util.TreeSet<>(s.chars().mapToObj(c -> (char) c).toList())); int best = 0; for (int i = 0; i < distinct.size(); i++) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Trimming instead of rejecting
Once you keep letters x and y, you keep ALL of them. If filtering leaves 'aa' adjacent, the pair is simply invalid — you can't drop one 'a' to fix it, because that violates 'delete all or none of a letter'.
Explore the code comparisonHide the code comparison
Trimming instead of rejecting
Once you keep letters x and y, you keep ALL of them. If filtering leaves 'aa' adjacent, the pair is simply invalid — you can't drop one 'a' to fix it, because that violates 'delete all or none of a letter'.
Don't write this
t = [c for c in s if c in (x, y)]
# remove duplicates greedily (WRONG)
t = [t[k] for k in range(len(t)) if k == 0 or t[k] != t[k-1]]
best = max(best, len(t))Write this instead
t = [c for c in s if c in (x, y)]
if all(t[k] != t[k + 1] for k in range(len(t) - 1)) and len(t) > 1:
best = max(best, len(t))2Accepting one-letter results
A valid string needs exactly two distinct characters. Filtering to a pair where one letter is absent leaves a single-letter run that must not be counted.
Explore the code comparisonHide the code comparison
Accepting one-letter results
A valid string needs exactly two distinct characters. Filtering to a pair where one letter is absent leaves a single-letter run that must not be counted.
Don't write this
if (ok) best = Math.max(best, t.length());Write this instead
if (ok && t.length() > 1) best = Math.max(best, t.length());3Forgetting alternation entirely
Returning the longest two-letter subsequence without checking adjacency accepts strings like 'aabb', which are not valid.
Explore the code comparisonHide the code comparison
Forgetting alternation entirely
Returning the longest two-letter subsequence without checking adjacency accepts strings like 'aabb', which are not valid.
Don't write this
t = [c for c in s if c == x or c == y]
best = max(best, len(t))Write this instead
t = [c for c in s if c == x or c == y]
if all(t[k] != t[k + 1] for k in range(len(t) - 1)):
best = max(best, len(t))Revise
Carry the pattern into the interview
Pattern to remember
Enumerate letter pairs + alternation check
Code pattern to memorize
best = 0
for each pair (x, y) of distinct letters in s:
t = [c for c in s if c == x or c == y]
if t alternates (t[i] != t[i+1] for all i):
best = max(best, len(t))
return bestRules to remember
- 1You may delete all occurrences of any letter, but the survivors must be exactly two distinct letters.
- 2'Valid' means the kept string alternates —
t[i] != t[i+1]everywhere. - 3A valid alternating string of two letters automatically has length ≥ 2; if no pair alternates, answer is 0.
- 4Only consider letters that actually appear — pairing with an absent letter wastes work.
- 5Filtering preserves original order; never reorder the survivors.
Use this pattern when
- Restrict a string to a small fixed set of allowed symbols and test a local property
- The alphabet is tiny (≤ 26) so enumerating pairs is cheap
- You need the longest subsequence using exactly two symbols with an adjacency rule
- Deleting whole character classes (all of a letter) is permitted
Choose another pattern when
- Any number of distinct letters allowed → not this pairwise enumeration
- Deletions are limited / costed → becomes a DP, not free filtering
- Subarray (contiguous) required, not subsequence → sliding window instead
- Huge alphabet (k large) → O(k²·n) pair enumeration is too slow
Interview takeaway
Because the answer uses only two distinct letters, you can brute-force over the ≤ 325 letter pairs, filter the string to each pair, and keep the longest one that alternates. Tiny alphabet turns an apparently exponential 'choose a subsequence' problem into a quadratic-in-alphabet scan.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternSmall-alphabet enumeration. When the answer is confined to a tiny fixed structure (here, exactly two letters from a 26-letter alphabet), enumerate that structure as the outer loop and let each choice force the rest. Turns an exponential subsequence search into O(k²·n).
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Two Characters with k distinctComing soonAllowing k distinct letters breaks the pairwise trick — needs a different model.
- Longest Substring Without Repeating CharactersComing soonContiguous version with a sliding window instead of pair filtering.
- Longest Substring with At Most Two Distinct CharactersComing soonContiguous and two-distinct, but no alternation rule — sliding window.
- Distinct Echo SubstringsComing soonAnother 'restrict and enumerate' string structure problem.