Skip to main content

139. Word Break

mediumAsked at HubSpot

HubSpot 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 Alex Chen, 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 <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s and wordDict[i] consist of only lowercase English letters.
  • All the strings of wordDict are unique.

Examples

Example 1

Input
s = "leetcode", wordDict = ["leet","code"]
Output
true

Explanation: 'leetcode' can be segmented as 'leet code'.

Example 2

Input
s = "applepenapple", wordDict = ["apple","pen"]
Output
true

Explanation: '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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

Drill Word Break and other HubSpot interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →