Word Break

🎯

Word Break

mediumDPAmazonFacebookGoogle

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.

💡 This problem is a classic example of dynamic programming where beginners often struggle to see how to break down the problem into smaller subproblems and how to efficiently check all possible partitions without redundant work.

📋

Problem Statement

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

💡

Example

Input"s = \"leetcode\", wordDict = [\"leet\", \"code\"]"

Outputtrue

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

Input"s = \"applepenapple\", wordDict = [\"apple\", \"pen\"]"

Outputtrue

The string can be segmented as "apple pen apple".

Input"s = \"catsandog\", wordDict = [\"cats\", \"dog\", \"sand\", \"and\", \"cat\"]"

Outputfalse

No segmentation of the string into dictionary words is possible.

• Empty string s → true (empty string can be segmented trivially)
• Dictionary contains the entire string as one word → true
• String with repeated characters not in dictionary → false
• String where only partial prefixes are in dictionary but no full segmentation → false

🔁

Why DP?

Why greedy fails:

For example, s = "catsandog" and dictionary = ["cats", "cat", "and", "sand", "dog"]. A greedy approach might pick "cats" first, then fail to segment the rest, missing the correct segmentation "cat sand dog". Greedy fails because local optimal choices don't guarantee global solution.

DP state:

dp[i] = true if the substring s[0:i] can be segmented into dictionary words, false otherwise.

Recurrence:dp[i] = OR over j in [0, i) of (dp[j] AND s[j:i] in wordDict)

To know if s[0:i] can be segmented, check if there exists a j < i where s[0:j] can be segmented (dp[j] is true) and the substring s[j:i] is a dictionary word.

⚠️

Common Mistakes

Not handling empty string base case

Algorithm returns false incorrectly for empty input

✅ Initialize dp[0] = True or return True for empty string

Using list instead of set for dictionary lookup

Substring checks become O(n) causing timeouts

✅ Convert wordDict to a set for O(1) lookups

Not breaking inner loop after dp[i] is set True

Unnecessary computations increase runtime

✅ Add break after dp[i] = True

Incorrect substring indices causing off-by-one errors

Wrong segmentation results or runtime errors

✅ Carefully use substring slicing with correct start and end indices

Not memoizing in top-down approach

Exponential time and TLE

✅ Use a memo dictionary or map to cache results

🧠

Brute Force (Pure Recursion)

💡 This approach helps understand the problem by trying all possible segmentations without optimization, revealing the exponential complexity and overlapping subproblems.

Intuition

Try every possible prefix of the string and recursively check if the remaining suffix can be segmented.

Algorithm

1. Start from the beginning of the string.
2. Try every possible prefix and check if it is in the dictionary.
3. If prefix is valid, recursively check the suffix.
4. Return true if any segmentation leads to the end of the string.

💡 The recursion tree grows exponentially because each prefix choice leads to multiple suffix checks, making it hard to track without memoization.

Recurrence:f(i) = OR over j in [i+1, n] of (s[i:j] in wordDict AND f(j))

</>

Code

def wordBreak(s, wordDict):
    word_set = set(wordDict)
    def backtrack(start):
        if start == len(s):
            return True
        for end in range(start + 1, len(s) + 1):
            if s[start:end] in word_set and backtrack(end):
                return True
        return False

# Driver code
if __name__ == '__main__':
    s = "leetcode"
    wordDict = ["leet", "code"]
    print(wordBreak(s, wordDict))

Line Notes

word_set = set(wordDict)Convert list to set for O(1) lookup of words

def backtrack(start):Define recursive helper to check segmentation from index start

if start == len(s):Base case: reached end means successful segmentation

for end in range(start + 1, len(s) + 1):Try all possible prefixes starting at start

if s[start:end] in word_set and backtrack(end):If prefix is valid and suffix can be segmented, return True

return FalseNo valid segmentation found from this start index

import java.util.*;
public class WordBreak {
    public static boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        return backtrack(s, 0, wordSet);
    }
    private static boolean backtrack(String s, int start, Set<String> wordSet) {
        if (start == s.length()) return true;
        for (int end = start + 1; end <= s.length(); end++) {
            if (wordSet.contains(s.substring(start, end)) && backtrack(s, end, wordSet)) {
                return true;
            }
        }
        return false;
    }
    public static void main(String[] args) {
        String s = "leetcode";
        List<String> wordDict = Arrays.asList("leet", "code");
        System.out.println(wordBreak(s, wordDict));
    }
}

Line Notes

Set<String> wordSet = new HashSet<>(wordDict);Use HashSet for fast word lookup

private static boolean backtrack(String s, int start, Set<String> wordSet)Recursive helper to check segmentation from start

if (start == s.length()) return true;Base case: full string segmented

for (int end = start + 1; end <= s.length(); end++)Try all prefixes from start

if (wordSet.contains(s.substring(start, end)) && backtrack(s, end, wordSet))Check prefix and recurse on suffix

return false;No valid segmentation found

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
bool backtrack(const string &s, int start, const unordered_set<string> &wordSet) {
    if (start == s.size()) return true;
    for (int end = start + 1; end <= (int)s.size(); ++end) {
        if (wordSet.count(s.substr(start, end - start)) && backtrack(s, end, wordSet)) {
            return true;
        }
    }
    return false;
}
int main() {
    string s = "leetcode";
    vector<string> wordDict = {"leet", "code"};
    unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
    cout << (backtrack(s, 0, wordSet) ? "true" : "false") << endl;
    return 0;
}

Line Notes

unordered_set<string> wordSet(wordDict.begin(), wordDict.end());Create hash set for O(1) word lookup

bool backtrack(const string &s, int start, const unordered_set<string> &wordSet)Recursive function to check segmentation from start

if (start == s.size()) return true;Base case: entire string segmented

for (int end = start + 1; end <= (int)s.size(); ++end)Try all prefixes starting at start

if (wordSet.count(s.substr(start, end - start)) && backtrack(s, end, wordSet))Check prefix and recurse on suffix

return false;No valid segmentation found

function wordBreak(s, wordDict) {
    const wordSet = new Set(wordDict);
    function backtrack(start) {
        if (start === s.length) return true;
        for (let end = start + 1; end <= s.length; end++) {
            if (wordSet.has(s.substring(start, end)) && backtrack(end)) {
                return true;
            }
        }
        return false;
    }
    return backtrack(0);
}

// Test
console.log(wordBreak("leetcode", ["leet", "code"]));

Line Notes

const wordSet = new Set(wordDict);Use Set for O(1) word lookup

function backtrack(start)Recursive helper to check segmentation from start

if (start === s.length) return true;Base case: full segmentation achieved

for (let end = start + 1; end <= s.length; end++)Try all prefixes starting at start

if (wordSet.has(s.substring(start, end)) && backtrack(end))Check prefix and recurse on suffix

return false;No valid segmentation found

⏱

Complexity

TimeO(2^n) in worst case due to exploring all segmentations

SpaceO(n) recursion stack depth

Each index can branch into multiple recursive calls, leading to exponential time. Space is linear due to recursion depth.

💡 For n=20, this could mean over a million calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem structure before optimizing.

🧠

Top-Down DP with Memoization

💡 Memoization avoids recomputing results for the same substring start indices, drastically improving performance while keeping the recursive structure.

Intuition

Store results of subproblems (start indices) so that each substring is solved once.

Algorithm

1. Initialize a memo dictionary to store results for start indices.
2. Recursively check prefixes as before.
3. Before recursion, check if result for start is memoized.
4. Return memoized result if available, else compute and store it.

💡 Memoization prunes the recursion tree by caching results, turning exponential time into polynomial.

Recurrence:f(i) = OR over j in [i+1, n] of (s[i:j] in wordDict AND f(j)) with memoization

</>

Code

def wordBreak(s, wordDict):
    word_set = set(wordDict)
    memo = {}
    def backtrack(start):
        if start == len(s):
            return True
        if start in memo:
            return memo[start]
        for end in range(start + 1, len(s) + 1):
            if s[start:end] in word_set and backtrack(end):
                memo[start] = True
                return True
        memo[start] = False
        return False

# Driver code
if __name__ == '__main__':
    s = "leetcode"
    wordDict = ["leet", "code"]
    print(wordBreak(s, wordDict))

Line Notes

memo = {}Initialize memo dictionary to cache results

if start in memo:Return cached result if available to avoid recomputation

memo[start] = TrueCache positive result before returning

memo[start] = FalseCache negative result before returning

for end in range(start + 1, len(s) + 1):Try all prefixes from start

import java.util.*;
public class WordBreak {
    public static boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        Map<Integer, Boolean> memo = new HashMap<>();
        return backtrack(s, 0, wordSet, memo);
    }
    private static boolean backtrack(String s, int start, Set<String> wordSet, Map<Integer, Boolean> memo) {
        if (start == s.length()) return true;
        if (memo.containsKey(start)) return memo.get(start);
        for (int end = start + 1; end <= s.length(); end++) {
            if (wordSet.contains(s.substring(start, end)) && backtrack(s, end, wordSet, memo)) {
                memo.put(start, true);
                return true;
            }
        }
        memo.put(start, false);
        return false;
    }
    public static void main(String[] args) {
        String s = "leetcode";
        List<String> wordDict = Arrays.asList("leet", "code");
        System.out.println(wordBreak(s, wordDict));
    }
}

Line Notes

Map<Integer, Boolean> memo = new HashMap<>();Memo map caches results for start indices

if (memo.containsKey(start)) return memo.get(start);Return cached result if present

memo.put(start, true);Cache positive result

memo.put(start, false);Cache negative result

for (int end = start + 1; end <= s.length(); end++)Try all prefixes

#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <vector>
using namespace std;
bool backtrack(const string &s, int start, const unordered_set<string> &wordSet, unordered_map<int, bool> &memo) {
    if (start == s.size()) return true;
    if (memo.count(start)) return memo[start];
    for (int end = start + 1; end <= (int)s.size(); ++end) {
        if (wordSet.count(s.substr(start, end - start)) && backtrack(s, end, wordSet, memo)) {
            memo[start] = true;
            return true;
        }
    }
    memo[start] = false;
    return false;
}
int main() {
    string s = "leetcode";
    vector<string> wordDict = {"leet", "code"};
    unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
    unordered_map<int, bool> memo;
    cout << (backtrack(s, 0, wordSet, memo) ? "true" : "false") << endl;
    return 0;
}

Line Notes

unordered_map<int, bool> memo;Memo map caches results for start indices

if (memo.count(start)) return memo[start];Return cached result if available

memo[start] = true;Cache positive result

memo[start] = false;Cache negative result

for (int end = start + 1; end <= (int)s.size(); ++end)Try all prefixes

function wordBreak(s, wordDict) {
    const wordSet = new Set(wordDict);
    const memo = new Map();
    function backtrack(start) {
        if (start === s.length) return true;
        if (memo.has(start)) return memo.get(start);
        for (let end = start + 1; end <= s.length; end++) {
            if (wordSet.has(s.substring(start, end)) && backtrack(end)) {
                memo.set(start, true);
                return true;
            }
        }
        memo.set(start, false);
        return false;
    }
    return backtrack(0);
}

// Test
console.log(wordBreak("leetcode", ["leet", "code"]));

Line Notes

const memo = new Map();Memo map caches results for start indices

if (memo.has(start)) return memo.get(start);Return cached result if present

memo.set(start, true);Cache positive result

memo.set(start, false);Cache negative result

for (let end = start + 1; end <= s.length; end++)Try all prefixes

⏱

Complexity

TimeO(n^3) worst case due to substring extraction and checking all partitions

SpaceO(n) recursion stack + O(n) memo storage

Memoization ensures each start index is computed once, but substring operations cost O(n), leading to cubic time in worst case.

💡 For n=20, this reduces calls from millions to at most 20, but substring checks still add overhead.

Interview Verdict: Accepted

This approach is efficient enough for most inputs and is a common interview solution.

🧠

Bottom-Up DP (Tabulation)

💡 This approach builds the solution iteratively from smaller substrings to the full string, avoiding recursion and making the process clearer and often faster.

Intuition

Use a boolean dp array where dp[i] indicates if s[0:i] can be segmented, and fill it from left to right using previously computed results.

Algorithm

1. Initialize dp array of size n+1 with False, set dp[0] = True for empty string.
2. For each index i from 1 to n, check all j < i.
3. If dp[j] is True and s[j:i] is in dictionary, set dp[i] = True.
4. Return dp[n] as the final answer.

💡 The dp array accumulates knowledge about which prefixes can be segmented, ensuring no repeated work.

Recurrence:dp[i] = OR over j in [0, i) of (dp[j] AND s[j:i] in wordDict)

</>

Code

def wordBreak(s, wordDict):
    word_set = set(wordDict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    return dp[n]

# Driver code
if __name__ == '__main__':
    s = "leetcode"
    wordDict = ["leet", "code"]
    print(wordBreak(s, wordDict))

Line Notes

dp = [False] * (n + 1)Initialize dp array to track segmentability of prefixes

dp[0] = TrueEmpty string is always segmentable

for i in range(1, n + 1)Iterate over all prefix lengths

for j in range(i)Check all possible split points

if dp[j] and s[j:i] in word_setIf prefix up to j is segmentable and suffix is a word, mark dp[i]

breakStop early once dp[i] is True

import java.util.*;
public class WordBreak {
    public static boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
    public static void main(String[] args) {
        String s = "leetcode";
        List<String> wordDict = Arrays.asList("leet", "code");
        System.out.println(wordBreak(s, wordDict));
    }
}

Line Notes

boolean[] dp = new boolean[n + 1];DP array to store segmentability of prefixes

dp[0] = true;Empty string is segmentable

for (int i = 1; i <= n; i++)Iterate over prefix lengths

for (int j = 0; j < i; j++)Check all split points

if (dp[j] && wordSet.contains(s.substring(j, i)))If prefix and suffix valid, mark dp[i]

break;Stop checking once dp[i] is true

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
bool wordBreak(string s, vector<string> &wordDict) {
    unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
    int n = s.size();
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (dp[j] && wordSet.count(s.substr(j, i - j))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
}
int main() {
    string s = "leetcode";
    vector<string> wordDict = {"leet", "code"};
    cout << (wordBreak(s, wordDict) ? "true" : "false") << endl;
    return 0;
}

Line Notes

vector<bool> dp(n + 1, false);DP array to track segmentability

dp[0] = true;Empty string is segmentable

for (int i = 1; i <= n; ++i)Iterate over prefix lengths

for (int j = 0; j < i; ++j)Check all split points

if (dp[j] && wordSet.count(s.substr(j, i - j)))If prefix and suffix valid, mark dp[i]

break;Stop checking once dp[i] is true

function wordBreak(s, wordDict) {
    const wordSet = new Set(wordDict);
    const n = s.length;
    const dp = new Array(n + 1).fill(false);
    dp[0] = true;
    for (let i = 1; i <= n; i++) {
        for (let j = 0; j < i; j++) {
            if (dp[j] && wordSet.has(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
}

// Test
console.log(wordBreak("leetcode", ["leet", "code"]));

Line Notes

const dp = new Array(n + 1).fill(false);DP array to track segmentability

dp[0] = true;Empty string is segmentable

for (let i = 1; i <= n; i++)Iterate over prefix lengths

for (let j = 0; j < i; j++)Check all split points

if (dp[j] && wordSet.has(s.substring(j, i)))If prefix and suffix valid, mark dp[i]

break;Stop checking once dp[i] is true

⏱

Complexity

TimeO(n^3) worst case due to substring extraction and nested loops

SpaceO(n) for dp array

For each i, we check all j < i and substring extraction costs O(n), leading to cubic time.

💡 For n=20, this is about 8000 operations, which is efficient for interviews.

Interview Verdict: Accepted

This is the standard iterative DP solution often preferred in interviews for clarity and efficiency.

🧠

Bottom-Up DP with Trie or Prefix Optimization (Space Optimized)

💡 By using a Trie or limiting checks to only dictionary word lengths, we reduce unnecessary substring checks and optimize space and time.

Intuition

Instead of checking all j, only check substring lengths that match dictionary words, reducing iterations.

Algorithm

1. Precompute the set of word lengths in the dictionary.
2. Initialize dp array with dp[0] = True.
3. For each index i, check only substrings of lengths in word lengths set.
4. If dp[i - length] is True and substring s[i-length:i] is in dictionary, set dp[i] = True.
5. Return dp[n].

💡 This reduces the number of substring checks drastically, improving runtime especially when dictionary words have limited lengths.

Recurrence:dp[i] = OR over length in wordLengths of (dp[i - length] AND s[i-length:i] in wordDict)

</>

Code

def wordBreak(s, wordDict):
    word_set = set(wordDict)
    word_lengths = set(len(word) for word in wordDict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for length in word_lengths:
            if length <= i and dp[i - length] and s[i - length:i] in word_set:
                dp[i] = True
                break
    return dp[n]

# Driver code
if __name__ == '__main__':
    s = "leetcode"
    wordDict = ["leet", "code"]
    print(wordBreak(s, wordDict))

Line Notes

word_lengths = set(len(word) for word in wordDict)Precompute unique word lengths to limit substring checks

dp = [False] * (n + 1)DP array to track segmentability

dp[0] = TrueEmpty string is segmentable

for i in range(1, n + 1)Iterate over prefix lengths

for length in word_lengthsCheck only substrings of dictionary word lengths

if length <= i and dp[i - length] and s[i - length:i] in word_setCheck if substring is valid and prefix is segmentable

import java.util.*;
public class WordBreak {
    public static boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        Set<Integer> wordLengths = new HashSet<>();
        for (String word : wordDict) wordLengths.add(word.length());
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int length : wordLengths) {
                if (length <= i && dp[i - length] && wordSet.contains(s.substring(i - length, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
    public static void main(String[] args) {
        String s = "leetcode";
        List<String> wordDict = Arrays.asList("leet", "code");
        System.out.println(wordBreak(s, wordDict));
    }
}

Line Notes

Set<Integer> wordLengths = new HashSet<>();Store unique word lengths to optimize checks

boolean[] dp = new boolean[n + 1];DP array for segmentability

dp[0] = true;Empty string is segmentable

for (int i = 1; i <= n; i++)Iterate over prefix lengths

for (int length : wordLengths)Check only dictionary word lengths

if (length <= i && dp[i - length] && wordSet.contains(s.substring(i - length, i)))Check substring validity and prefix dp

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
bool wordBreak(string s, vector<string> &wordDict) {
    unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
    unordered_set<int> wordLengths;
    for (const string &w : wordDict) wordLengths.insert(w.size());
    int n = s.size();
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    for (int i = 1; i <= n; ++i) {
        for (int length : wordLengths) {
            if (length <= i && dp[i - length] && wordSet.count(s.substr(i - length, length))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
}
int main() {
    string s = "leetcode";
    vector<string> wordDict = {"leet", "code"};
    cout << (wordBreak(s, wordDict) ? "true" : "false") << endl;
    return 0;
}

Line Notes

unordered_set<int> wordLengths;Store unique word lengths for optimization

vector<bool> dp(n + 1, false);DP array for segmentability

dp[0] = true;Empty string is segmentable

for (int i = 1; i <= n; ++i)Iterate over prefix lengths

for (int length : wordLengths)Check only dictionary word lengths

if (length <= i && dp[i - length] && wordSet.count(s.substr(i - length, length)))Check substring and prefix dp

function wordBreak(s, wordDict) {
    const wordSet = new Set(wordDict);
    const wordLengths = new Set(wordDict.map(w => w.length));
    const n = s.length;
    const dp = new Array(n + 1).fill(false);
    dp[0] = true;
    for (let i = 1; i <= n; i++) {
        for (let length of wordLengths) {
            if (length <= i && dp[i - length] && wordSet.has(s.substring(i - length, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
}

// Test
console.log(wordBreak("leetcode", ["leet", "code"]));

Line Notes

const wordLengths = new Set(wordDict.map(w => w.length));Precompute unique word lengths

const dp = new Array(n + 1).fill(false);DP array for segmentability

dp[0] = true;Empty string is segmentable

for (let i = 1; i <= n; i++)Iterate over prefix lengths

for (let length of wordLengths)Check only dictionary word lengths

if (length <= i && dp[i - length] && wordSet.has(s.substring(i - length, i)))Check substring and prefix dp

⏱

Complexity

TimeO(n * m * k) where m is number of unique word lengths and k is max word length for substring extraction

SpaceO(n) for dp array

By limiting substring checks to dictionary word lengths, we reduce the inner loop iterations, improving efficiency.

💡 For dictionaries with small max word length, this can be significantly faster than naive DP.

Interview Verdict: Accepted

This approach is a practical optimization often discussed in interviews to improve DP solutions.

📊

All Approaches - One-Glance Tradeoffs

💡 Bottom-up DP with substring length optimization is recommended for 95% of interviews due to clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	Yes	Mention only - never code
2. Top-Down DP with Memoization	O(n^3)	O(n) memo + recursion stack	Possible but less than brute force	Yes	Good for explaining optimization
3. Bottom-Up DP (Tabulation)	O(n^3)	O(n)	No	Yes	Preferred approach to code
4. Bottom-Up DP with Word Length Optimization	O(n * m * k) (m = unique word lengths, k = max word length)	O(n)	No	Yes	Mention as optimization if time permits

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and constraints.Explain the brute force recursive approach to show understanding.Introduce memoization to optimize overlapping subproblems.Present bottom-up DP as an iterative alternative.Discuss possible optimizations like limiting substring checks.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Ability to identify overlapping subproblems, implement DP correctly, optimize code, and handle edge cases.

Common Follow-ups

• How to print all possible segmentations? → Use backtracking with DP to reconstruct paths.
• What if dictionary is very large? → Use Trie for prefix matching to optimize lookups.

💡 These follow-ups test deeper understanding of DP reconstruction and data structure optimizations.

🔍

Pattern Recognition

When to Use

1) Asked if string can be segmented into dictionary words; 2) Overlapping subproblems with substring checks; 3) Boolean DP state; 4) Need to check all prefixes or suffixes.

Signature Phrases

can be segmenteddictionary wordsbreak the string

NOT This Pattern When

Problems that require counting partitions or generating all partitions (Word Break II) are related but require different DP states.

Similar Problems

Decode Ways - similar DP on string with different constraintsPalindrome Partitioning - partition string into palindromes instead of dictionary words

Practice

1. Given the following code for minimum cost climbing stairs, what is the value of curr during the first iteration of the loop when cost = [10, 15, 20]?

easy

A. 30

B. 25

C. 20

D. 15

Solution

1. Step 1: Initialize variables

   prev2 = cost[0] = 10, prev1 = cost[1] = 15

2. Step 2: Calculate curr at i=2

   curr = cost[2] + min(prev1, prev2) = 20 + min(15, 10) = 20 + 10 = 30

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   curr is sum of current cost plus min of previous two costs [OK]

Hint: curr = cost[i] + min(prev1, prev2) at each iteration [OK]

Common Mistakes:

• Mixing prev1 and prev2 values
• Off-by-one errors in loop
• Returning intermediate curr instead of final min

2. Consider the following buggy code snippet for maxProfit. Which line contains the subtle bug that causes incorrect results on some inputs?

medium

A. Line with 'if k >= n // 2:' condition

B. Line with 'for j in range(1, k + 1):' loop iterating forwards

C. Line initializing buy array with -float('inf')

D. Line returning sell[k] at the end

Solution

1. Step 1: Identify iteration order in inner loop

   The inner loop iterates forwards from 1 to k, which causes buy[j] to use updated sell[j-1] from the same iteration, corrupting state.

2. Step 2: Correct iteration order

   Iterating backwards from k down to 1 prevents premature overwriting of states, preserving correctness.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Forward iteration overwrites dp states too early [OK]

Hint: Inner loop must run backwards to avoid state overwrite [OK]

Common Mistakes:

• Forgetting to iterate backwards in space optimized DP

3. What is the time and space complexity of the optimal space-optimized dynamic programming solution for the Best Time -- Transaction Fee problem, given n prices?

medium

A. Time: O(n), Space: O(1) by tracking only two states per iteration

B. Time: O(n²), Space: O(n) due to nested loops and DP table

C. Time: O(n), Space: O(n) because of memoization cache or DP array

D. Time: O(n log n), Space: O(1) due to sorting and constant state variables

Solution

1. Step 1: Identify time complexity

   The algorithm iterates once over the prices array, performing constant time operations per element -> O(n).

2. Step 2: Identify space complexity

   Only two variables (cash and hold) are maintained and updated each iteration -> O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass and constant state variables confirm O(n) time and O(1) space [OK]

Hint: Only two states tracked, no DP table needed [OK]

Common Mistakes:

• Confusing recursion stack space with DP space
• Assuming DP table stored for all days

4. If you are allowed to complete as many transactions as you like (buy and sell multiple times), which modification to the algorithm below correctly computes the maximum profit?

hard

A. Sum up all positive differences between consecutive days' prices to accumulate profit from every profitable transaction.

B. Keep the same code but multiply the final max_profit by the number of transactions allowed.

C. Use the same min_price tracking but reset min_price to current price after each profitable sale.

D. Use nested loops to check all pairs of buy and sell days and pick the maximum sum of profits from multiple transactions.

Solution

1. Step 1: Understand multiple transactions scenario

   When unlimited transactions are allowed, profit is sum of all positive price differences between consecutive days.

2. Step 2: Identify correct algorithm modification

   Summing positive differences directly captures all profitable trades without complex state tracking.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Summing positive daily gains yields max profit with unlimited transactions [OK]

Hint: Sum all positive consecutive price differences [OK]

Common Mistakes:

• Multiplying single transaction profit by transaction count
• Resetting min_price incorrectly
• Using nested loops causing inefficiency

5. Suppose the stock trading problem is modified so that you must pay a transaction fee for each sale. Which of the following changes to the state machine DP solution correctly accounts for the fee while maintaining optimal profit calculation?

hard

A. Add the fee to both buying and selling updates to ensure fee is counted twice

B. Subtract the fee from the buying price when updating holding: holding = max(holding, prev_not_holding - prices[i] - fee)

C. Subtract the fee from the selling price when updating not_holding: not_holding = max(not_holding, holding + prices[i] - fee)

D. Ignore the fee in DP and subtract total fee at the end from final profit

Solution

1. Step 1: Understand fee impact

   The fee applies on each sale, so it should reduce the profit gained when selling.

2. Step 2: Adjust DP transitions

   Subtract fee from the selling transition: not_holding = max(not_holding, holding + prices[i] - fee). Buying price remains unchanged.

3. Step 3: Why other options fail

   Subtracting fee on buying overcharges; adding fee twice double counts; ignoring fee until end breaks DP correctness.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Fee reduces profit only on selling, correctly modeled in not_holding update [OK]

Hint: Fee applies only on selling, subtract from selling transition [OK]

Common Mistakes:

• Subtracting fee on buying instead of selling
• Double counting fee on buy and sell
• Ignoring fee in DP transitions