Add 0 and as dummy break points. Now we have points, and we need to fully break the string. Base case: (no break needed between adjacent points). Fill by increasing gap: gap = 2, 3, ..., . For each with gap , search . Time: , Space: . Track alongside . Add sentinel break points at 0 and n to handle boundaries cleanly. The actual breaks are between sentinels.
Time complexity: .
Space complexity: .