First Valid Word Segmentation
Reported by candidates from Amazon's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Amazon reported this one in July 2025, and the input sizes are the whole story. With s up to 500 characters and a dictionary of 5000 words, trying every split blindly will blow up on inputs like repeated a's. It's word break with a twist: you return the first segmentation in shortest-prefix-first order, not just true or false. If you blank on the memo, StealthCoder is the invisible safety net running during the live OA. But the pattern is small enough to own tonight.
The problem
Given a continuous lowercase string s and an array dictionary representing the words accepted by isWord, split s into a sequence of dictionary words whose concatenation is exactly s. At each position, consider possible next words by increasing end position, so the shortest possible next prefix is tried first. Return the first complete segmentation found by that order. At least one valid segmentation is guaranteed. Function segmentWords(s: String, dictionary: String[]) → String[] Examples Example 1 s = "myhousehavecat" dictionary = ["my","house","have","cat"] return = ["my","house","have","cat"] Each returned piece is accepted by the dictionary, and their concatenation is myhousehavecat. Example 2 s = "aaaa" dictionary = ["a","aa"] return = ["a","a","a","a"] Both one- and two-character words are valid, but increasing end positions try a before aa. Repeating that choice reaches a complete segmentation. Example 3 s = "catsanddog" dictionary = ["cats","dog","sand","and","cat"] return = ["cat","sand","dog"] At index 0, cat ends before cats and can lead to a complete segmentation, so it begins the returned sequence. Constraints 1 <= s.length <= 500, and s contains only lowercase English letters. 1 <= dictionary.length <= 5000. Dictionary words are distinct, contain only lowercase English letters, and have lengths from 1 through 50. The total number of characters across dictionary is at most 10^5. At least one valid segmentation of s exists. Possible next words are considered by increasing end position.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick is DFS with memoization on the start index, trying end positions in increasing order. Put the dictionary in a hash set, and since words max out at 50 characters, cap each end position at start + 50. That keeps work near 500 * 50 lookups. The key detail is the failure memo. Store which start indices can't reach the end, so you never re-explore a dead branch. The first time DFS reaches index n, return the path, and it's automatically the lexicographically-first-by-shortest-prefix answer. Common pitfall: a plain boolean DP loses the path ordering, and plain recursion without a dead-index memo goes exponential on strings like aaaa...b. Another pitfall is returning the shortest total word count, which isn't what's asked. Example 3 shows it: cat beats cats because it's tried first and succeeds. If you freeze live, StealthCoder is the hedge, but you should be able to write this in ten lines.
If this hits your live OA and you blank, StealthCoder solves it in seconds, invisible to the proctor.
You can drill First Valid Word Segmentation cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built by an Amazon engineer who would have shipped this the night before his JPMorgan OA if he'd had it.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Amazon's OA.
Amazon reuses patterns across OAs. Built by an Amazon engineer who would have shipped this the night before his JPMorgan OA if he'd had it. Works on HackerRank, CodeSignal, CoderPad, and Karat.
First Valid Word Segmentation FAQ
What's the trick in First Valid Word Segmentation?+
DFS from index 0, try each end position in increasing order, and check the substring against a hash set. Memoize start indices that fail so you never retry them. The first path that reaches the end of the string is your answer, because shortest-first order is built into the loop.
Why does brute force fail here?+
With s up to 500 and words like a and aa, the number of possible splits grows exponentially. A string of repeated a's ending in a bad character forces recursion to explore every combination. The dead-index memo cuts it to at most 500 distinct start states.
How do I keep the lookups fast?+
Load the dictionary into a set and cap the end position at start plus 50, since no word is longer than 50. That bounds each state to 50 substring checks. You can also track the max word length from the dictionary instead of hardcoding it.
Is word break still asked in Amazon OAs?+
This variant was reported for Amazon in July 2025, so yes, the family is alive. The twist is returning the actual first segmentation, not a boolean. Know both the word break DP and the DFS with memo and path reconstruction.
How do I prepare in 48 hours?+
Write the memoized DFS from scratch twice, then test it on aaaa with a and aa, and on catsanddog. Check that cat is chosen over cats. Then practice a failing case where the greedy shortest word dead-ends and you must backtrack.