Pattern Reference
String Construction
"Build smallest/greatest string under constraints. Lexicographically smallest after swaps, K-th lexicographically smallest."
Loading...
Deep Dive Tutorial
Edit distance: dp[i][j] = min ops to convert s[0..i] to t[0..j]. Base: dp[i][0]=i, dp[0][j]=j. Transition: if s[i]==t[j], dp[i][j]=dp[i-1][j-1]; else min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1). Word ladder: BFS where each step changes one character to get a valid word. String construction from pieces: dp[i] = can build s[0..i] using dictionary words.
Edit distance and word break templates
// Edit distance — O(m*n)
function editDistance(s, t) {
const m = s.length, n = t.length;
const dp = Array.from({length: m+1}, (_, i) => Array(n+1).fill(0).map((_, j) => i||j));
// dp[i][0]=i, dp[0][j]=j is implicit from the fill above; fix it:
for (let i = 0; i <= m; i++) dp[i][0] = i;
for (let j = 0; j <= n; j++) dp[0][j] = j;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (s[i-1] === t[j-1]) dp[i][j] = dp[i-1][j-1];
else dp[i][j] = 1 + Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
}
}
return dp[m][n];
}
// Word break — can s be segmented using wordDict?
function wordBreak(s, wordDict) {
const set = new Set(wordDict);
const dp = new Array(s.length + 1).fill(false);
dp[0] = true;
for (let i = 1; i <= s.length; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && set.has(s.slice(j, i))) { dp[i] = true; break; }
}
}
return dp[s.length];
}Worked Problems
construction
String construction patterns:
- Edit distance: 2D DP, transitions on match vs mismatch
- Word ladder: BFS on word graph, change 1 char per step
- Decode ways: 1D DP, try 1-digit and 2-digit decodings
- Anagram steps: frequency difference sum
Edit distance variants: Weighted costs (ASCII delete sum), only insertions/deletions (LCS-based: cost = m+n - 2*LCS), one string to empty (just delete all).
Key optimization: For edit distance with only insert/delete, use LCS: min_ops = m + n - 2 * LCS(s, t).
- Edit distance: 2D DP, transitions on match vs mismatch
- Word ladder: BFS on word graph, change 1 char per step
- Decode ways: 1D DP, try 1-digit and 2-digit decodings
- Anagram steps: frequency difference sum
Edit distance variants: Weighted costs (ASCII delete sum), only insertions/deletions (LCS-based: cost = m+n - 2*LCS), one string to empty (just delete all).
Key optimization: For edit distance with only insert/delete, use LCS: min_ops = m + n - 2 * LCS(s, t).