Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Decide whether the login attempt can be split into a sequence of the given passwords (each reusable any number of times), and if so reconstruct that sequence. This is the Word Break problem with path reconstruction: scan from the front, and at each position try every password that matches as a prefix, recursing on the remainder. The key to making it fast is memoising the positions from which no valid split exists, so each suffix is explored once. Output the passwords space-separated, or "WRONG PASSWORD" if no split works. O(N · K · L) time where N = attempt length, K = number of passwords, L = max password length.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognise this as Word Break, see why greedy prefix matching fails, and add memoisation on failed start positions to avoid exponential blow-up — plus careful reconstruction and output formatting.
Where candidates slip
Greedily taking the first matching password without backtracking, forgetting to memoise failed indices (TLE on inputs like passwords {a, aa, aaa} with attempt aaaa...b), or mis-formatting the WRONG PASSWORD output.
How to stand out
Show a concrete input where greedy fails, derive the recursion, explain that memoising failed suffixes makes it O(N·K·L), and note the bottom-up DP with parent pointers as an iterative alternative.
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 previewcanSplit(start)start == len?YesNoExplore 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 3
Brute Force — Backtracking Without Memo (Exponential)
1Hint 1Explore hintHide hint
From the current index, try every password that matches the string starting there; for each, recurse on the index just past it.
2Hint 2Explore hintHide hint
If the index reaches the end, you've consumed the whole attempt — success; bubble the chosen passwords back up.
3Hint 3Explore hintHide hint
On adversarial inputs like passwords {a, aa, aaa} and attempt 'aaaa...ab', the same suffix index is reached through many prefix combinations, so this recomputes exponentially.
A · Core idea
Define solve(start) = a list of passwords whose concatenation equals attempt[start..], or null if impossible.
Recursion. If start equals the length, the suffix is empty and we succeed with an empty list. Otherwise, for each password pw, if attempt starts with pw at position start, recurse on solve(start + pw.length()). If that returns a list (not null), prepend pw and return. If no password leads to success, return null.
Why greed fails (and why this backtracks). Taking the first matching password unconditionally can strand the remainder. Consider passwords {ab, abc} and attempt abcd where only cd is also a password: greedily matching ab then cd works, but if cd were absent and only d+something worked via abc, greed on ab would dead-end. Backtracking tries the next password whenever a branch fails, so it never gets stuck on a bad first choice.
Why it's exponential. Inputs like {a, aa, aaa} with aaaa…ab let countless prefix combinations land on the same suffix start, each re-explored from scratch. The cure is to remember which start indices are hopeless — the next approach.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
passwords = [hello, planet], attempt = "helloworld"Interactive diagram
Why memoisation is needed
solve(0)Different prefix paths converge on the same start index, re-exploring it.
WRONG PASSWORDC · Code with teaching comments
Reference implementation previewpublic String passwordCracker(List<String> passwords, String attempt) { List<String> path = solve(passwords, attempt, 0); return path == null ? "WRONG PASSWORD" : String.join(" ", path); } Explore the full codeHide the full code
D · Why it works and complexityO(K^N) worst case timeO(N) recursion + output spaceOpen the invariant and proofExplore the proofHide the proof
The recursion is correct on its own; the disaster is purely repeated work. The same suffix start index gets re-derived through exponentially many prefix paths — exactly the overlapping-subproblem signature that says 'memoise me'.
ComplexityO(K^N) worst case time, O(N) recursion + output space — With K passwords, each position can branch K ways and the depth is up to N, so the search tree is exponential. Overlapping prefixes mean the same start index is re-explored along many paths.
E · Edge cases and pitfalls3Greedily committing to the first match without backtracking.Explore edge casesHide edge cases
Pitfalls
- Greedily committing to the first match without backtracking.
- No memo → exponential time on overlapping-prefix inputs.
- Returning a boolean only and losing the reconstructed sequence.
Approach 2 of 3 · Optimal
Memoised Backtracking on Failed Suffixes (Optimal)
1Hint 1Explore hintHide hint
Add a set 'failed' of start indices already proven unsplittable; bail out immediately if the current start is in it.
2Hint 2Explore hintHide hint
Because there are only N+1 distinct start indices, each is fully explored at most once — that's what bounds the work.
3Hint 3Explore hintHide hint
Per index you try K passwords, each requiring an O(L) prefix comparison, giving O(N·K·L) overall.
A · Core idea
Take the brute-force recursion and add one cache: a set failed of start indices from which no valid split exists.
The change. At the top of solve(start), if start ∈ failed, return null instantly. Before returning null (no password worked), insert start into failed. That single memo guarantees each start index is fully expanded at most once.
Why caching *failures* is enough. Successes return immediately and unwind the whole stack, so a successful index is never revisited. Only failing indices get re-reached (through different prefix paths), so caching just the failures is sufficient — and it's exactly the set that caused the exponential blow-up.
Complexity. With the memo, the work is bounded by (number of start indices) × (work per index) = (N+1) × (K passwords × O(L) prefix check) = O(N·K·L). For N ≤ 2000, K ≤ 10, L ≤ 10 that's tiny.
Reconstruction. When a recursive call returns a non-null list, prepend the password we matched and propagate up. The top-level call returns the full ordered list, which we join with spaces; null becomes WRONG PASSWORD.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
passwords = [a, aa, aaa], attempt = "aaaaab"Array state
reach b
solve(5) fails → failed={5}
WRONG PASSWORDC · Code with teaching comments
D · Why it works and complexityO(N · K · L) timeO(N) spaceOpen the invariant and proofExplore the proofHide the proof
You don't need to memoise everything — only the dead ends. Successful paths self-prune by returning straight to the top, so a set of failing start indices is the minimal cache that kills the exponential behaviour.
ComplexityO(N · K · L) time, O(N) space — There are N+1 start indices. Each is processed once (subsequent visits short-circuit via the failed set). Processing an index tries K passwords with O(L) match checks → O(N·K·L) time, O(N) for the memo and recursion depth.
E · Edge cases and pitfalls7attempt equals one password exactly — First match consumes the whole string; solve(len) returns [], so output is that single password.Explore edge casesHide edge cases
Edge cases handled
attempt equals one password exactlyFirst match consumes the whole string; solve(len) returns [], so output is that single password.attempt = "" (empty)solve(0) hits start==len immediately → empty list → joins to empty string (handle per harness).passwords contain duplicatesHarmless; the first matching copy is used, others are skipped.passwords = [a, aa, aaa], attempt = "aaaaab"Trailing 'b' unmatchable; memo prevents blow-up → WRONG PASSWORD.
Pitfalls
- Caching visited indices instead of failed ones and accidentally suppressing a valid path — only cache confirmed failures.
- Recursion depth on a 2000-char attempt split into 1-char passwords — convert to the iterative DP below if the stack is a concern.
- Joining with the wrong separator or wrong casing for WRONG PASSWORD.
Approach 3 of 3
Bottom-Up DP with Parent Pointers
1Hint 1Explore hintHide hint
Let reachable[i] mean 'attempt[i..] up to some boundary is splittable starting at i'. Work the other way: dp[i] = can attempt[0..i) be split.
2Hint 2Explore hintHide hint
dp[0] = true. For each end i, if dp[j] is true and attempt[j..i) is a password, set dp[i] = true and record parent[i] = j (and which password).
3Hint 3Explore hintHide hint
If dp[N] is true, walk parent pointers from N back to 0 to rebuild the password sequence, then reverse it.
A · Core idea
Recast the recursion as a forward DP over prefix lengths, avoiding recursion entirely.
State. dp[i] is true iff attempt[0..i) (the first i characters) can be segmented into passwords. dp[0] = true (empty prefix).
Transition. For each end index i from 1 to N, look at each password pw. If pw ends exactly at i (i.e. i ≥ len(pw) and attempt[i-len..i) == pw) and dp[i-len] is true, then dp[i] is true. Record parent[i] = i - len and chosen[i] = pw so we can rebuild the path.
Reconstruction. If dp[N] is true, start at i = N, repeatedly emit chosen[i] and jump to parent[i] until reaching 0, then reverse the collected passwords. Otherwise output WRONG PASSWORD.
Why prefer it sometimes. It's iterative (no deep recursion on long attempts), and the reachability array makes the logic easy to reason about. Same asymptotic cost as the memoised recursion; pick whichever reads more clearly for you.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
passwords = [we, do, what], attempt = "wedowhat"Array state
after 'we','do'
dp[0],dp[2],dp[4] true
we do whatC · Code with teaching comments
Reference implementation previewpublic String passwordCracker(List<String> passwords, String s) { int n = s.length(); boolean[] dp = new boolean[n + 1]; int[] parent = new int[n + 1]; String[] chosen = new String[n + 1];Explore the full codeHide the full code
D · Why it works and complexityO(N · K · L) timeO(N) spaceOpen the invariant and proofExplore the proofHide the proof
Word Break has a clean forward formulation: a prefix of length i is splittable iff some earlier splittable prefix is followed by a password ending at i. Storing one parent pointer per index turns the yes/no DP into a path-reconstructing one for free.
ComplexityO(N · K · L) time, O(N) space — Outer loop over N end positions, inner over K passwords with O(L) comparison → O(N·K·L). Arrays dp and parent are O(N); reconstruction is O(N).
E · Edge cases and pitfalls6no split exists — dp[n] stays false → WRONG PASSWORD without touching parent pointers.Explore edge casesHide edge cases
Edge cases handled
no split existsdp[n] stays false → WRONG PASSWORD without touching parent pointers.multiple passwords end at the same ibreak keeps the first; any valid choice is fine for an arbitrary segmentation.attempt = single passworddp[len] becomes true via dp[0]; reconstruction emits the lone password.
Pitfalls
- Forgetting to reverse the reconstructed list — back-pointers yield it end-to-front.
- Using `break` but then needing ALL segmentations — break only gives one (which is all this problem wants).
- Indexing s.startsWith at the wrong offset (use i-len, the password's start).
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic String passwordCracker(List<String> passwords, String attempt) { Set<Integer> failed = new HashSet<>(); List<String> path = solve(passwords, attempt, 0, failed); return path == null ? "WRONG PASSWORD" : String.join(" ", path); }Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Greedy first-match without backtracking
Committing to the first password that matches can strand the rest of the string even when another split succeeds. You must try alternatives on failure.
Explore the code comparisonHide the code comparison
Greedy first-match without backtracking
Committing to the first password that matches can strand the rest of the string even when another split succeeds. You must try alternatives on failure.
Don't write this
i = 0
out = []
while i < len(s):
for pw in passwords:
if s.startswith(pw, i):
out.append(pw); i += len(pw); break
else:
return 'WRONG PASSWORD' # gave up without backtrackingWrite this instead
def solve(start):
if start == len(s): return []
for pw in passwords:
if s.startswith(pw, start):
rest = solve(start + len(pw))
if rest is not None: return [pw] + rest
return None2No memoisation of dead ends
Without caching failed start indices, inputs like {a, aa, aaa} on 'aaaa…ab' re-explore the same suffix exponentially and time out.
Explore the code comparisonHide the code comparison
No memoisation of dead ends
Without caching failed start indices, inputs like {a, aa, aaa} on 'aaaa…ab' re-explore the same suffix exponentially and time out.
Don't write this
def solve(start):
if start == len(s): return []
for pw in passwords:
if s.startswith(pw, start):
rest = solve(start + len(pw))
if rest is not None: return [pw] + rest
return None # recomputes failing suffixes foreverWrite this instead
failed = set()
def solve(start):
if start == len(s): return []
if start in failed: return None
for pw in passwords:
if s.startswith(pw, start):
rest = solve(start + len(pw))
if rest is not None: return [pw] + rest
failed.add(start)
return None3Wrong failure string
The judge expects the exact token 'WRONG PASSWORD'. Lowercase, extra spaces, or a different message fails even when the logic is correct.
Explore the code comparisonHide the code comparison
Wrong failure string
The judge expects the exact token 'WRONG PASSWORD'. Lowercase, extra spaces, or a different message fails even when the logic is correct.
Don't write this
return "wrong password"; // or "WRONG_PASSWORD"Write this instead
return "WRONG PASSWORD";Revise
Carry the pattern into the interview
Pattern to remember
Word Break (segmentation) with memoised suffixes and path reconstruction
Code pattern to memorize
canSplit(start):
if start == len(attempt): return [] # empty suffix → success
if start in failed: return null # memoised dead end
for pw in passwords:
if attempt.startsWith(pw, start):
rest = canSplit(start + len(pw))
if rest != null: return [pw] + rest
failed.add(start) # remember this start fails
return nullRules to remember
- 1Memoise failed start indices, not just visited ones — without it, overlapping prefixes (e.g.
a,aa) cause exponential re-exploration. - 2Passwords may be reused any number of times — it's unbounded segmentation, so don't 'consume' a password.
- 3Match must be anchored at the current index (
startsWith(pw, start)), and a successful split must consume the string exactly to the end. - 4On total failure print exactly
WRONG PASSWORD(uppercase, single space) — a formatting slip fails the test. - 5Greedily taking the first matching password is wrong; you must be able to backtrack when a choice leads to a dead end.
Use this pattern when
- Can a target string be segmented into pieces drawn from a dictionary?
- Pieces are reusable and you need either a yes/no or one valid segmentation
- Overlapping prefixes make greedy matching fail and demand backtracking
- You can phrase progress as 'consume a valid prefix, recurse on the rest'
Choose another pattern when
- Each piece may be used at most once → bitmask / assignment DP, not free segmentation
- You need ALL segmentations enumerated → backtracking without the pruning power of plain memo (count can be exponential)
- Pieces can overlap in the target (not a clean concatenation) → different model
- The dictionary is enormous and pieces long → build a trie/Aho–Corasick for prefix matching
Interview takeaway
Segmentation problems collapse to 'consume a matching prefix, recurse on the remainder'. The single optimisation that turns exponential into polynomial is memoising the start indices that fail — once a suffix is known unsplittable, never re-enter it.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternPassword Cracker is Word Break with path reconstruction. Model it as 'consume a matching prefix, recurse on the rest', backtrack on dead ends, and memoise the start indices that fail to turn exponential search into O(N·K·L). The iterative dp[i]+parent-pointer formulation is the stack-safe equivalent.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Word BreakThe yes/no version — same segmentation DP without reconstruction.
- Word Break IIComing soonReturn ALL segmentations — backtracking with memo on the lists of splits.
- Concatenated WordsComing soonFind dictionary words that are themselves concatenations — Word Break applied per word.