139. Word Break
mediumAsked at HubSpotHubSpot uses Word Break to test bottom-up dynamic programming and substring reachability — reasoning patterns that map directly to parsing HubSpot's expression language and evaluating segmented workflow conditions.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in HubSpot loops.
- Glassdoor (2026-Q1)— HubSpot SWE candidates cite Word Break as an onsite medium problem testing DP with string segmentation.
- Blind (2025-10)— Listed in HubSpot interview threads as a medium-difficulty DP problem focusing on reachability reasoning.
Problem
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. Note that the same word in the dictionary may be reused multiple times in the segmentation.
Constraints
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s and wordDict[i] consist of only lowercase English letters.All the strings of wordDict are unique.
Examples
Example 1
s = "leetcode", wordDict = ["leet","code"]trueExplanation: 'leetcode' can be segmented as 'leet code'.
Example 2
s = "applepenapple", wordDict = ["apple","pen"]trueExplanation: 'applepenapple' = 'apple pen apple'. A word may be reused.
Approaches
1. Bottom-up DP
dp[i] = true if s[0..i-1] can be segmented using wordDict. For each position i, check all j < i where dp[j] is true and s[j..i-1] is in the dictionary. Base case: dp[0] = true (empty string is trivially segmented).
- Time
- O(n² * k) where k is average word length for substring lookup
- Space
- O(n)
function wordBreak(s, wordDict) {
const wordSet = new Set(wordDict);
const n = s.length;
const dp = new Array(n + 1).fill(false);
dp[0] = true; // empty prefix is always segmentable
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; // no need to check further j values
}
}
}
return dp[n];
}Tradeoff: Clear O(n²) DP with O(n) state. Converting wordDict to a Set gives O(1) average lookup per substring check. The break after finding a valid j avoids redundant work. This is the canonical expected answer at HubSpot.
HubSpot-specific tips
Frame the DP recurrence before coding: 'dp[i] is true if any split point j exists such that dp[j] is true and s[j..i-1] is a dictionary word.' HubSpot interviewers appreciate when you state base cases explicitly: 'dp[0] = true represents the empty string, which is trivially valid.' They often ask: 'What if s is very long and wordDict is large?' — connect to trie optimization for O(n * maxWordLen).
Common mistakes
- Forgetting dp[0] = true — without it, no position ever becomes reachable.
- Using wordDict.includes() instead of a Set — O(m) per lookup makes the overall algorithm O(n² * m).
- Off-by-one in s.substring(j, i) — the second argument is exclusive in JavaScript, so s.substring(j, i) returns s[j..i-1], correct.
- Not breaking after finding a valid j — functional but wastes work; adding break is a correctness-neutral optimization that shows attention to efficiency.
Follow-up questions
An interviewer at HubSpot may pivot to one of these next:
- Word Break II (LC 140) — return all possible segmentations, not just whether one exists.
- How would you use a Trie to improve lookup efficiency for large word dictionaries?
- What's the minimum number of word breaks needed to segment s? (DP with count tracking.)
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why is dp[0] = true?
It represents the empty prefix, which is trivially segmentable. Without it, dp[word.length] would never be set true for the first word, and nothing further could be reached.
What's the time complexity of substring lookup in a Set?
JavaScript's Set.has() on strings is O(k) where k is the string length (hashing the string). The inner loop's substring(j, i) is also O(k), so each (i,j) pair is O(k) total.
Can words repeat in the segmentation?
Yes — the problem explicitly states 'the same word may be reused.' The DP handles this naturally since it checks all substrings from any reachable position.