LogoBytesFor Developers
HomeBytesheetsRoadmapsUI TemplatesUI ToolsStack Discussion
10 Topics
Chapter•480 Minutes

Hard DSA — Advanced Dynamic Programming & Complex String Matching

Master complex state-transition dynamic programming, multi-dimensional memoization, wildcard matching algorithms, and advanced string evaluation patterns.

01. Edit Distance (Levenshtein Distance)

Difficulty:HardPattern:2D Dynamic ProgrammingTime:O(m * n)Space:O(m * n)

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2 using insertions, deletions, or substitutions.

How It Works & Algorithmic Design

Solves using 2D Dynamic Programming Grid Matching:

  1. DP State: Define dp[i][j] as the minimum edit distance between word1[0...i-1] and word2[0...j-1].
  2. Base Cases: dp[i][0] = i (deleting all characters from word1) and dp[0][j] = j (inserting all characters into word1).
  3. State Transitions:
    • If word1[i-1] === word2[j-1], no operation is needed: dp[i][j] = dp[i-1][j-1].
    • Otherwise, take the minimum of 3 operations plus 1:
      • Insert: dp[i][j-1] + 1
      • Delete: dp[i-1][j] + 1
      • Replace: dp[i-1][j-1] + 1

Why This Approach Works Best

Computes exact minimum edit distance in $O(m \times n)$ time and $O(m \times n)$ space, which can be space-optimized to $O(\min(m, n))$ using rolling arrays.

Example Walkthrough
Input: word1 = "horse", word2 = "ros"
Target conversion.
Operations Trace: horse -> rorse (replace 'h' with 'r') -> rose (remove 'r') -> ros (remove 'e')
3 operations required.
Output: 3
Minimum operations.

Answer: Edit Distance 2D DP implementation

function minDistance(word1, word2) {
  const m = word1.length, n = word2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  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 (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
      }
    }
  }
  return dp[m][n];
}
💡 Build dynamic programming table evaluating insert, delete, and replace operational paths.
Key Takeaways
  • Minimizes structural distance across two sequences.
  • Sub-problem operations: Insert (left cell), Delete (top cell), Replace (diagonal cell).
  • Time complexity $O(m \times n)$.

02. Regular Expression Matching

Difficulty:HardPattern:2D Regex State DPTime:O(s * p)Space:O(s * p)

Given an input string s and a pattern p, implement regular expression matching with support for '.' (matches any single character) and '*' (matches zero or more of the preceding element).

How It Works & Algorithmic Design

Solves using 2D Dynamic Programming with Wildcard Expansion:

  1. DP Table: Let dp[i][j] be boolean matching status of s[0...i-1] and p[0...j-1].
  2. Base Case: dp[0][0] = true. Handle patterns like a*b* matching empty string s.
  3. Matching Rules:
    • If p[j-1] === s[i-1] or p[j-1] === '.': dp[i][j] = dp[i-1][j-1].
    • If p[j-1] === '*':
      • Zero occurrences of preceding char: dp[i][j] = dp[i][j-2].
      • One/more occurrences (if preceding char matches s[i-1] or is '.'): dp[i][j] = dp[i][j] || dp[i-1][j].

Why This Approach Works Best

Avoids infinite backtracking loops and evaluates complex regex state graphs in $O(|s| \times |p|)$ time and space.

Example Walkthrough
Input: s = "aa", p = "a*"
'*' matches zero or more 'a's.
Pattern Expansion: 'a*' expands to "aa", matching string s exactly.
Valid regex match.
Output: true
Matches completely.

Answer: Regular Expression Matching implementation

function isMatch(s, p) {
  const m = s.length, n = p.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));
  dp[0][0] = true;
  for (let j = 2; j <= n; j += 2) {
    if (p[j - 1] === '*') dp[0][j] = dp[0][j - 2];
  }
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (p[j - 1] === '*' ) {
        dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s[i - 1] === p[j - 2] || p[j - 2] === '.'));
      } else {
        dp[i][j] = dp[i - 1][j - 1] && (s[i - 1] === p[j - 1] || p[j - 1] === '.');
      }
    }
  }
  return dp[m][n];
}
💡 Build DP match matrix evaluating single character match and asterisk wildcard expansions.
Key Takeaways
  • Asterisk '*' operates on the preceding character.
  • Two choices for '*': zero matches (dp[i][j-2]) or extension match (dp[i-1][j]).
  • Optimal linear-squared complexity $O(|s| \times |p|)$.

03. Wildcard Matching

Difficulty:HardPattern:Greedy Star PointerTime:O(s * p)Space:O(1)

Given an input string s and a pattern p, implement wildcard pattern matching with support for '?' (matches any single character) and '*' (matches any sequence of characters, including empty sequence).

How It Works & Algorithmic Design

Solves using Greedy Two Pointers with Backtracking Positions:

  1. Pointers: sIdx = 0, pIdx = 0, match = 0, starIdx = -1.
  2. Traversal:
    • Characters match or p[pIdx] === '?': advance both sIdx++, pIdx++.
    • p[pIdx] === '*': save star checkpoint starIdx = pIdx, match = sIdx, advance pIdx++.
    • Mismatch after star: reset pIdx = starIdx + 1, advance match++, set sIdx = match.
    • Otherwise: mismatch without star $\to$ return false.
  3. Post Check: Skip trailing '*' in pattern. Return sIdx === s.length && pIdx === p.length.

Why This Approach Works Best

Greedy two-pointer pointer tracking with star backtracking runs in $O(|s| \times |p|)$ worst-case and $O(1)$ constant space.

Example Walkthrough
Input: s = "cb", p = "?a"
'?' matches 'c', but 'a' != 'b'.
Output: false
Pattern mismatch.

Answer: Wildcard Matching using Greedy Star Pointers

function isMatch(s, p) {
  let sIdx = 0, pIdx = 0, match = 0, starIdx = -1;
  while (sIdx < s.length) {
    if (pIdx < p.length && (p[pIdx] === '?' || s[sIdx] === p[pIdx])) {
      sIdx++; pIdx++;
    } else if (pIdx < p.length && p[pIdx] === '*') {
      starIdx = pIdx; match = sIdx; pIdx++;
    } else if (starIdx !== -1) {
      pIdx = starIdx + 1; match++; sIdx = match;
    } else return false;
  }
  while (pIdx < p.length && p[pIdx] === '*') pIdx++;
  return pIdx === p.length;
}
💡 Match string characters and track last star pattern index for constant-space backtracking.
Key Takeaways
  • Wildcard '*' matches any sequence without needing a predecessor.
  • Greedy star position tracking achieves $O(1)$ space complexity.
  • Significantly faster in practice compared to 2D DP table recursion.

04. Distinct Subsequences

Difficulty:HardPattern:Subsequence Count DPTime:O(s * t)Space:O(s * t)

Given two strings s and t, return the number of distinct subsequences of s which equals t.

How It Works & Algorithmic Design

Solves using 2D Subsequence Frequency Dynamic Programming:

  1. DP Definition: dp[i][j] = number of distinct subsequences of s[0...i-1] that match t[0...j-1].
  2. Base Case: dp[i][0] = 1 (an empty string t is a subsequence of any s prefix exactly once).
  3. Transition:
    • If s[i-1] === t[j-1]: dp[i][j] = dp[i-1][j-1] + dp[i-1][j] (sum of matching character choice plus skipping character choice).
    • Else: dp[i][j] = dp[i-1][j] (must skip s[i-1]).

Why This Approach Works Best

Evaluates total subsequence counts systematically in $O(|s| \times |t|)$ time and space.

Example Walkthrough
Input: s = "rabbbit", t = "rabbit"
Target subsequence matching.
Combinations: There are 3 distinct ways to drop one 'b' from "rabbbit" to leave "rabbit".
Subsequence count is 3.
Output: 3
3 distinct subsequences.

Answer: Distinct Subsequences DP implementation

function numDistinct(s, t) {
  const m = s.length, n = t.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 0; i <= m; i++) dp[i][0] = 1;
  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] + dp[i - 1][j];
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  return dp[m][n];
}
💡 Count matching subsequences by building dynamic programming table.
Key Takeaways
  • Base case empty target t gives dp[i][0] = 1.
  • Matching characters allow choice between including or skipping s[i-1].
  • Time complexity is $O(|s| \times |t|)$.

05. Burst Balloons

Difficulty:HardPattern:Interval DPTime:O(n^3)Space:O(n^2)

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. If you burst balloon i you will get nums[i - 1] * nums[i] * nums[i + 1] coins. Return the maximum coins you can collect.

How It Works & Algorithmic Design

Solves using Reverse Interval Dynamic Programming:

  1. Padding: Pad input nums with $1$ at both ends: [1, ...nums, 1].
  2. Reverse Decision: Think of picking the LAST balloon $k$ to burst in interval [i, j]:
    • Coins gained from picking balloon $k$ last = nums[i-1] * nums[k] * nums[j+1] + dp[i][k-1] + dp[k+1][j].
  3. DP Interval Loop: Expand sub-array length len from $1$ to $n$, evaluating all choices of $k$ to maximize total coins.

Why This Approach Works Best

Reversing decision order makes sub-problems independent, solving the problem in $O(n^3)$ time and $O(n^2)$ space.

Example Walkthrough
Input: nums = [3, 1, 5, 8]
Balloons list.
Optimal Sequence: Burst 1 -> Burst 5 -> Burst 3 -> Burst 8
Yields 167 total coins.
Output: 167
Maximum coins.

Answer: Burst Balloons Interval DP implementation

function maxCoins(nums) {
  const A = [1, ...nums, 1];
  const n = A.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let len = 1; len <= nums.length; len++) {
    for (let i = 1; i <= nums.length - len + 1; i++) {
      const j = i + len - 1;
      for (let k = i; k <= j; k++) {
        dp[i][j] = Math.max(dp[i][j], A[i - 1] * A[k] * A[j + 1] + dp[i][k - 1] + dp[k + 1][j]);
      }
    }
  }
  return dp[1][nums.length];
}
💡 Compute optimal coins bottom-up across sub-array lengths by determining the last balloon to burst.
Key Takeaways
  • Reversing decision logic (selecting last burst balloon) keeps sub-problems decoupled.
  • Pad boundary array with 1 at both index ends.
  • Time complexity $O(n^3)$.

06. Minimum Window Substring

Difficulty:HardPattern:Sliding WindowTime:O(|s| + |t|)Space:O(|s| + |t|)

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window.

How It Works & Algorithmic Design

Solves using Variable Sliding Window with Frequency Counts:

  1. Frequency Map: Build frequency target map for string t. Maintain required = map.size.
  2. Expand Right: Move right pointer over s:
    • Decrement character count in map. If count reaches zero, increment formed++.
  3. Contract Left: While formed === required:
    • Update min window substring bounds if smaller.
    • Shrink left pointer: increment map count. If count becomes $> 0$, decrement formed--.

Why This Approach Works Best

Achieves optimal $O(|s| + |t|)$ linear time complexity and $O(|s| + |t|)$ space without testing all $O(s^2)$ sub-string pairs.

Example Walkthrough
Input: s = "ADOBECODEBANC", t = "ABC"
Find smallest substring containing A, B, C.
Window Shrink: Window "BANC" contains 'A', 'B', 'C' with length 4.
Smallest valid window found.
Output: "BANC"
Minimum window substring.

Answer: Minimum Window Substring implementation

function minWindow(s, t) {
  if (!s || !t) return '';
  const tCount = {};
  for (const ch of t) tCount[ch] = (tCount[ch] || 0) + 1;
  let required = Object.keys(tCount).length;
  let left = 0, right = 0, formed = 0;
  const windowCounts = {};
  let ans = [-1, 0, 0];
  while (right < s.length) {
    const c = s[right];
    windowCounts[c] = (windowCounts[c] || 0) + 1;
    if (tCount[c] && windowCounts[c] === tCount[c]) formed++;
    while (left <= right && formed === required) {
      const cLeft = s[left];
      if (ans[0] === -1 || right - left + 1 < ans[0]) ans = [right - left + 1, left, right];
      windowCounts[cLeft]--;
      if (tCount[cLeft] && windowCounts[cLeft] < tCount[cLeft]) formed--;
      left++;
    }
    right++;
  }
  return ans[0] === -1 ? '' : s.substring(ans[1], ans[2] + 1);
}
💡 Expand right window edge to fulfill target character counts, then contract left edge to find minimal size.
Key Takeaways
  • Use formed match counter to avoid $O(26)$ frequency comparison inside loops.
  • Two pointers advance linearly across input string.
  • Linear time complexity $O(|s| + |t|)$.

07. Serialize and Deserialize Binary Tree

Difficulty:HardPattern:Pre-Order DFS SerializationTime:O(n)Space:O(n)

Design an algorithm to serialize and deserialize a binary tree into a string format and reconstruct the exact original tree structure.

How It Works & Algorithmic Design

Solves using Pre-Order Traversal with Sentinel Markers:

  1. Serialization: Perform DFS pre-order traversal. For each non-null node append node.val + ','. For null nodes append 'null,'.
  2. Deserialization: Split serialized string by ',' into a list/queue of tokens.
    • Read next token: if token equals 'null', return null.
    • Otherwise, create node = new TreeNode(Number(token)).
    • node.left = deserialize().
    • node.right = deserialize().
    • Return node.

Why This Approach Works Best

Pre-order sentinel traversal uniquely identifies tree structure without needing both In-Order and Pre-Order arrays, executing in $O(n)$ time and $O(n)$ space.

Example Walkthrough
Input Tree: [1, 2, 3, null, null, 4, 5]
Binary tree.
Serialized String: "1,2,null,null,3,4,null,null,5,null,null,"
Pre-order string with sentinel nulls.
Deserialized Result: Reconstructed identical binary tree.
Tree reference match.

Answer: Tree Serialization & Deserialization implementation

function serialize(root) {
  if (!root) return 'null';
  return `${root.val},${serialize(root.left)},${serialize(root.right)}`;
}

function deserialize(data) {
  const nodes = data.split(',');
  function buildTree() {
    const val = nodes.shift();
    if (val === 'null') return null;
    const node = { val: Number(val), left: null, right: null };
    node.left = buildTree();
    node.right = buildTree();
    return node;
  }
  return buildTree();
}
💡 Convert tree nodes to pre-order comma-separated string and reconstruct iteratively via token queue.
Key Takeaways
  • Sentinel null markers retain structural information during serialization.
  • Pre-order token streams can be parsed using simple recursive queue consumers.
  • Linear execution time $O(n)$.

08. Word Break II

Difficulty:HardPattern:Memoized DFS BacktrackingTime:O(2^n)Space:O(2^n)

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

How It Works & Algorithmic Design

Solves using DFS Backtracking with Hash Map Memoization:

  1. Memoization Map: memo[index] stores list of valid sentences formable from s[index...].
  2. DFS Function dfs(start):
    • Base Case: if start === s.length, return [""].
    • If start in memo, return memo[start].
    • Loop end from start + 1 to s.length:
      • Extract word = s.substring(start, end).
      • If wordDict.has(word):
        • Recurse subSentences = dfs(end).
        • Append word + (sub ? " " + sub : "") to res.
  3. Return: memo[0].

Why This Approach Works Best

Memoization prunes duplicate invalid search branches, preventing exponential catastrophic backtracking.

Example Walkthrough
Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Target text and words.
Sentences: ["cats and dog", "cat sand dog"]
Valid reconstructed sentence paths.
Output: ["cats and dog", "cat sand dog"]
Result array.

Answer: Word Break II Memoized DFS implementation

function wordBreak(s, wordDict) {
  const set = new Set(wordDict);
  const memo = new Map();
  function dfs(start) {
    if (memo.has(start)) return memo.get(start);
    if (start === s.length) return [''];
    const res = [];
    for (let end = start + 1; end <= s.length; end++) {
      const word = s.substring(start, end);
      if (set.has(word)) {
        const subs = dfs(end);
        for (const sub of subs) {
          res.push(word + (sub ? ' ' + sub : ''));
        }
      }
    }
    memo.set(start, res);
    return res;
  }
  return dfs(0);
}
💡 Recursively construct sentences with dictionary words while storing suffix string results in a memoization map.
Key Takeaways
  • Use Hash Set for $O(1)$ word existence lookups.
  • Memoizing index search state cuts down repetitive sentence branching.
  • Exponential worst-case complexity $O(2^n)$ when all combinations are valid.

09. Palindrome Partitioning II

Difficulty:HardPattern:Center Expansion DPTime:O(n^2)Space:O(n)

Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s.

How It Works & Algorithmic Design

Solves using 1D Dynamic Programming with Center Expansion Palindrome Pre-Check:

  1. Min Cut Table: Let cuts[i] be the min cuts needed for substring s[0...i].
  2. Initialize: cuts[i] = i (maximum cuts needed).
  3. Center-Expansion Loop: For each center $i$ (both odd and even centers):
    • Expand outward while s[left] === s[right]:
      • If left === 0, cuts[right] = 0 (entire prefix is a palindrome).
      • Else, cuts[right] = Math.min(cuts[right], cuts[left - 1] + 1).

Why This Approach Works Best

Expanding from centers avoids creating $O(n^2)$ 2D boolean palindrome matrices, optimizing runtime to $O(n^2)$ time and $O(n)$ space.

Example Walkthrough
Input: s = "aab"
Target string.
Optimal Cuts: "aa" | "b" (1 cut).
Palindromic parts.
Output: 1
1 cut.

Answer: Palindrome Partitioning II Center Expansion implementation

function minCut(s) {
  const n = s.length;
  const cuts = Array.from({ length: n }, (_, i) => i);
  for (let center = 0; center < n; center++) {
    expand(center, center);
    expand(center, center + 1);
  }
  function expand(left, right) {
    while (left >= 0 && right < n && s[left] === s[right]) {
      cuts[right] = left === 0 ? 0 : Math.min(cuts[right], cuts[left - 1] + 1);
      left--; right++;
    }
  }
  return cuts[n - 1];
}
💡 Expand palindrome centers outwards and update 1D cut array dynamically.
Key Takeaways
  • Center expansion tests both odd-length (i, i) and even-length (i, i+1) palindromes.
  • Eliminates auxiliary 2D boolean palindrome memo tables.
  • Executes in $O(n^2)$ time and $O(n)$ space.

10. Concatenated Words

Difficulty:HardPattern:DP / Set LookupsTime:O(N * L^2)Space:O(N * L)

Given an array of strings words (without duplicates), return all the concatenated words in the given list of words.

How It Works & Algorithmic Design

Solves using Word Length Sorting with Memoized Word Break Checking:

  1. Sort: Sort words by length in ascending order.
  2. Sub-word Verification: Maintain a set wordSet of previously processed shorter words.
  3. Word Break Check: For each word, execute DP canForm(word, wordSet):
    • Check if word can be partitioned into two or more words present in wordSet.
  4. Update: Add current word into wordSet.

Why This Approach Works Best

Processing shorter words first ensures a word can only be formed by strictly shorter constituent parts, optimizing performance across large dictionaries.

Example Walkthrough
Input: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
List of words.
Concatenated Words: "catsdogcats", "dogcatsdog", "ratcatdogcat"
Formed by joining smaller dictionary words.
Output: ["catsdogcats", "dogcatsdog", "ratcatdogcat"]
Result array.

Answer: Concatenated Words implementation

function findAllConcatenatedWordsInADict(words) {
  words.sort((a, b) => a.length - b.length);
  const wordSet = new Set();
  const res = [];
  function canForm(word) {
    if (wordSet.size === 0) return false;
    const dp = new Array(word.length + 1).fill(false);
    dp[0] = true;
    for (let i = 1; i <= word.length; i++) {
      for (let j = 0; j < i; j++) {
        if (dp[j] && wordSet.has(word.substring(j, i))) {
          dp[i] = true;
          break;
        }
      }
    }
    return dp[word.length];
  }
  for (const word of words) {
    if (canForm(word)) res.push(word);
    wordSet.add(word);
  }
  return res;
}
💡 Sort words by length and test if each word can be segmented using previously stored smaller words.
Key Takeaways
  • Sorting words by length builds set incrementally.
  • Reuses classic Word Break Dynamic Programming.
  • Runs in $O(N \cdot L^2)$ time where $N$ is word count and $L$ is word length.

STAY UPDATED WITH BYTES!

© 2026 Bytes4Dev. All rights reserved.

v.0.4.0