Word Break

📋

Problem

Imagine you receive a long string of characters and a dictionary of valid words. You want to know if you can split the string into a sequence of dictionary words, like breaking a secret code into meaningful words.

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Otherwise, return false. Input: string s, list of strings wordDict Output: boolean indicating if s can be segmented

1 ≤ s.length ≤ 10^51 ≤ wordDict.length ≤ 10^41 ≤ wordDict[i].length ≤ 20s and wordDict[i] consist of only lowercase English letters

Edge cases: Empty string s → true (empty string can be segmented trivially)Dictionary contains the entire string as one word → trueString with repeated characters not in dictionary → false

</>

IDE

def wordBreak(s: str, wordDict: list[str]) -> bool:public boolean wordBreak(String s, List<String> wordDict)bool wordBreak(string s, vector<string> wordDict)function wordBreak(s, wordDict)

def wordBreak(s, wordDict):
    # Write your solution here
    pass

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // Write your solution here
        return false;
    }
}

#include <vector>
#include <string>
using namespace std;

bool wordBreak(string s, vector<string> wordDict) {
    // Write your solution here
    return false;
}

function wordBreak(s, wordDict) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: falseDP array not initialized with dp[0] = true, so no segmentation possible.✅ Initialize dp[0] = true to represent empty string segmentation.

Wrong: trueGreedy approach accepts partial prefix matches without full segmentation.✅ Check all possible splits j < i, not just longest prefix.

Wrong: falseTreating dictionary words as 0/1 usage, disallowing reuse.✅ Allow dp[i] = true if any dp[j] true and s[j:i] in dictionary, regardless of previous usage.

Wrong: trueFailing to check full string in dictionary as a valid segmentation.✅ Ensure dp[len(s)] updates if s itself is in dictionary.

Wrong: TimeoutNaive recursion or substring extraction causing exponential or cubic time.✅ Use bottom-up DP with efficient substring checks or Trie optimization.

✓

Test Cases

Focus on handling empty strings and single-word dictionaries correctly.

Beware of greedy approaches and ensure you consider all possible segmentations.

Optimize your DP to avoid repeated substring extraction and exponential time.

t1_01basic

Input{"s":"leetcode","wordDict":["leet","code"]}

Expectedtrue

⏱ Performance - must finish in 2000ms

The string can be segmented as "leet code" which are both in the dictionary.

💡 Try using a boolean DP array where dp[i] means s[:i] can be segmented.

💡 Check if any prefix s[:j] is segmentable and s[j:i] is in the dictionary.

💡 dp[i] = dp[j] and s[j:i] in wordDict for some j < i.

Why it failed: Failed basic segmentation: likely missing dp state update or substring check. Fix by ensuring dp[i] updates when dp[j] is true and s[j:i] in dictionary.

✓ Basic segmentation logic is correct.

t1_02basic

Input{"s":"applepenapple","wordDict":["apple","pen"]}

Expectedtrue

⏱ Performance - must finish in 2000ms

The string can be segmented as "apple pen apple" which are all in the dictionary.

💡 Use DP to check all prefixes and substrings against the dictionary.

💡 Remember to check multiple segmentations, not just one split.

💡 dp[i] = true if dp[j] is true and s[j:i] in wordDict for some j < i.

Why it failed: Failed to handle multiple segments: likely only checking one split or missing dp propagation. Fix by iterating all j < i and updating dp[i] accordingly.

✓ Handles multiple segments correctly.

t2_01edge

Input{"s":"","wordDict":["a","b"]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Empty string can be segmented trivially (no words needed).

💡 Consider the base case dp[0] = true for empty string.

💡 Empty input should return true by definition.

💡 Initialize dp array with dp[0] = true to handle empty string.

Why it failed: Failed empty string case: likely dp[0] not initialized true. Fix by setting dp[0] = true to represent empty prefix segmentation.

✓ Correctly handles empty string base case.

t2_02edge

Input{"s":"apple","wordDict":["apple"]}

Expectedtrue

⏱ Performance - must finish in 2000ms

The entire string is one dictionary word, so segmentation is true.

💡 Check if the whole string is in the dictionary as a quick win.

💡 dp[len(s)] should be true if s itself is in wordDict.

💡 Ensure dp array covers full string length and checks full substring.

Why it failed: Failed full string dictionary match: likely missing check for s itself in wordDict. Fix by ensuring dp[len(s)] updates if s in dictionary.

✓ Correctly identifies full string in dictionary.

t2_03edge

Input{"s":"aaaaaaa","wordDict":["b"]}

Expectedfalse

⏱ Performance - must finish in 2000ms

String contains repeated characters not in dictionary, so segmentation is false.

💡 If no dictionary word matches any prefix, dp remains false except dp[0].

💡 Check that no substring s[j:i] is in wordDict.

💡 dp array should remain false except dp[0], resulting in false output.

Why it failed: Incorrectly returns true when no dictionary words match: likely missing substring membership check. Fix by verifying substring s[j:i] in dictionary before updating dp[i].

✓ Correctly returns false when no dictionary words match.

t3_01corner

Input{"s":"catsandog","wordDict":["cats","dog","sand","and","cat"]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Partial prefixes exist but no full segmentation possible.

💡 Partial matches don't guarantee full segmentation.

💡 Check all possible splits, not just greedy longest prefix.

💡 Avoid greedy approach; try all j < i for dp updates.

Why it failed: Greedy prefix matching leads to false positive. Fix by checking all possible splits j < i, not just longest prefix.

✓ Correctly rejects partial prefix matches without full segmentation.

t3_02corner

Input{"s":"aaaaaaa","wordDict":["aaaa","aaa"]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Multiple overlapping segmentations possible; must consider all splits.

💡 Check all splits, not just first or last match.

💡 DP must accumulate all valid segmentations.

💡 dp[i] = true if any dp[j] true and s[j:i] in dictionary.

Why it failed: Fails to consider multiple overlapping segmentations; likely stops early. Fix by continuing to check all j < i even after dp[i] is true.

✓ Handles overlapping segmentations correctly.

t3_03corner

Input{"s":"aaaaaaa","wordDict":["a","aa"]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 and unbounded usage; words can be reused unlimited times.

💡 Words can be reused multiple times; not 0/1 knapsack.

💡 DP must allow multiple uses of same dictionary word.

💡 Do not mark dp[i] false just because word used once; check all splits.

Why it failed: Incorrectly treats dictionary words as 0/1 usage; fails reuse. Fix by allowing dp[i] to be true if any dp[j] true and s[j:i] in dictionary, regardless of previous usage.

✓ Correctly allows unlimited reuse of dictionary words.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 tests O(n^3) brute force time complexity; must complete in 2s using optimized DP.

💡 Naive recursion or substring checks cause TLE.

💡 Use DP with efficient substring checks or Trie optimization.

💡 Avoid repeated substring extraction; use memoization or hashing.

Why it failed: TLE due to O(2^n) or O(n^3) brute force complexity. Fix by implementing bottom-up DP with prefix checks or Trie optimization.

✓ Efficient DP solution passes performance constraints.

Practice

1. Given the following code for maxProfit with k=1 and prices = [1, 5, 3], what is the final returned value?

easy

A. 4

B. 5

C. 3

D. 0

Solution

1. Step 1: Trace buy and sell arrays for each price

   Initialize buy=[-inf,-inf], sell=[0,0]. For price=1: buy[1]=max(-inf,0-1)=-1, sell[1]=0. For price=5: buy[1]=-1, sell[1]=max(0,-1+5)=4. For price=3: buy[1]=-1, sell[1]=max(4,-1+3)=4.

2. Step 2: Return sell[k]

   sell[1]=4 is the max profit after 1 transaction.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Profit from buying at 1 and selling at 5 is 4 [OK]

Hint: Track buy/sell updates backward for correct profit [OK]

Common Mistakes:

• Confusing buy and sell updates order
• Off-by-one in transaction index

2. Given the following code for the Jump Game II problem, what is the value of the variable jumps returned when the input is [2,1,1]?

easy

A. 3

B. 2

C. 1

D. 0

Solution

1. Step 1: Trace variables for input [2,1,1]

   n=3, loop i in [0,1]. - i=0: furthest = max(0, 0+2) = 2; i == current_end (0), so jumps = 1, current_end = 2 - i=1: furthest = max(2, 1+1) = 2; i != current_end (2), no jump increment Loop ends.

2. Step 2: Return jumps

   jumps = 1 is returned, meaning minimum 1 jump to reach the end.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   One jump from index 0 to last index covers entire array [OK]

Hint: Increment jumps only when i reaches current_end [OK]

Common Mistakes:

• Incrementing jumps too early or too late
• Off-by-one errors in loop range
• Misunderstanding when to update current_end

3. What is the time complexity of the optimal space-optimized bottom-up dynamic programming solution for the decoding ways problem, and why?

medium

A. O(n) but with O(n) auxiliary space for dp array

B. O(n^2) because each position checks all previous positions

C. O(2^n) due to recursive branching without memoization

D. O(n) because each character is processed once with constant checks

Solution

1. Step 1: Analyze loop iterations

   The code iterates through the string once, processing each character exactly once.

2. Step 2: Check operations per iteration

   Each iteration performs constant time checks for single and two-digit validity, no nested loops.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Linear scan with constant work per step -> O(n) time [OK]

Hint: One pass with constant work per character -> O(n) time [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Confusing recursion without memoization complexity

4. Consider the following buggy code for minimum cost climbing stairs. Which line contains the subtle bug that causes incorrect results on some inputs?

medium

A. Line 4: Loop range starting at 2

B. Line 7: Returning prev1 instead of min(prev1, prev2)

C. Line 6: Updating prev2 and prev1

D. Line 3: Initialization of prev2 and prev1

Solution

1. Step 1: Understand final return logic

   The top can be reached from either last step or second last step, so minimum of prev1 and prev2 must be returned.

2. Step 2: Identify incorrect return

   Returning only prev1 ignores the possibility that prev2 might be cheaper, causing wrong results.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Return min(prev1, prev2) to cover both possible last steps [OK]

Hint: Return min of last two costs, not just last [OK]

Common Mistakes:

• Forgetting min at return
• Misinitializing base cases
• Incorrect loop boundaries

5. Suppose the cooldown constraint is removed, allowing buying immediately after selling. Which modification to the DP state machine yields the correct optimal profit?

hard

A. Remove the 'cool' state and update 'hold' as max(hold, free - prices[i]) with free = max(free, free)

B. Use a greedy approach buying at every local minimum and selling at every local maximum

C. Keep 'cool' state but allow buying on cooldown day by updating hold = max(hold, cool - prices[i])

D. Remove 'cool' state and update hold = max(hold, free - prices[i]) with free = max(free, free)

Solution

1. Step 1: Understand cooldown removal effect

   Without cooldown, no need to track cooldown state; buying can happen immediately after selling.

2. Step 2: Adjust DP states

   Remove 'cool' state; hold updated as max(hold, free - prices[i]); free updated as max(free, free) (effectively unchanged).

3. Step 3: Why other options fail

   Keeping 'cool' or using greedy breaks correctness or adds unnecessary complexity.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Removing cooldown state matches classic Best Time II problem [OK]

Hint: No cooldown means no cooldown state needed [OK]

Common Mistakes:

• Trying to keep cooldown state unnecessarily
• Using greedy which fails on some inputs