[AlgoMastery]
Topics›String›String Interleaving
📖

String Interleaving

String
~20 min read
5 practice problems

Overview

String Interleaving problems involve determining if a string can be formed by interleaving two other strings while maintaining the relative order of characters from each string. These problems test your understanding of dynamic programming, string manipulation, and state transitions.

Key challenges:

  • Maintaining character order from both strings
  • Handling overlapping characters
  • Optimizing with memoization
  • Space-efficient solutions
  • Edge cases (empty strings, same characters)

Common interleaving problems include:

  • Check if string is interleaving of two strings
  • Find all interleaving combinations
  • Interleaving with constraints
  • Minimum operations to create interleaving
  • Interleaving subsequences

Pattern 1: Basic String Interleaving

Check if s3 is formed by interleaving s1 and s2.

Dynamic Programming approach:

function isInterleave(s1: string, s2: string, s3: string): boolean {
  const m = s1.length;
  const n = s2.length;
  
  if (m + n !== s3.length) return false;
  
  const dp: boolean[][] = Array(m + 1)
    .fill(null)
    .map(() => Array(n + 1).fill(false));
  
  dp[0][0] = true;
  
  // Initialize first row (using only s2)
  for (let j = 1; j <= n; j++) {
    dp[0][j] = dp[0][j - 1] && s2[j - 1] === s3[j - 1];
  }
  
  // Initialize first column (using only s1)
  for (let i = 1; i <= m; i++) {
    dp[i][0] = dp[i - 1][0] && s1[i - 1] === s3[i - 1];
  }
  
  // Fill DP table
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      dp[i][j] = 
        (dp[i - 1][j] && s1[i - 1] === s3[i + j - 1]) ||
        (dp[i][j - 1] && s2[j - 1] === s3[i + j - 1]);
    }
  }
  
  return dp[m][n];
}

Time: O(m n), Space: O(m n)

Space-optimized (1D DP):

function isInterleaveOptimized(s1: string, s2: string, s3: string): boolean {
  const m = s1.length;
  const n = s2.length;
  
  if (m + n !== s3.length) return false;
  
  const dp: boolean[] = new Array(n + 1).fill(false);
  dp[0] = true;
  
  // Initialize first row
  for (let j = 1; j <= n; j++) {
    dp[j] = dp[j - 1] && s2[j - 1] === s3[j - 1];
  }
  
  // Fill DP table
  for (let i = 1; i <= m; i++) {
    dp[0] = dp[0] && s1[i - 1] === s3[i - 1];
    
    for (let j = 1; j <= n; j++) {
      dp[j] = 
        (dp[j] && s1[i - 1] === s3[i + j - 1]) ||
        (dp[j - 1] && s2[j - 1] === s3[i + j - 1]);
    }
  }
  
  return dp[n];
}

Time: O(m * n), Space: O(min(m, n))

Pattern 2: Recursive with Memoization

Recursive approach with memoization.

function isInterleaveRecursive(s1: string, s2: string, s3: string): boolean {
  const m = s1.length;
  const n = s2.length;
  
  if (m + n !== s3.length) return false;
  
  const memo = new Map<string, boolean>();
  
  const dfs = (i: number, j: number, k: number): boolean => {
    if (k === s3.length) return true;
    
    const key = `${i},${j}`;
    if (memo.has(key)) return memo.get(key)!;
    
    let result = false;
    
    if (i < m && s1[i] === s3[k]) {
      result = result || dfs(i + 1, j, k + 1);
    }
    
    if (j < n && s2[j] === s3[k]) {
      result = result || dfs(i, j + 1, k + 1);
    }
    
    memo.set(key, result);
    return result;
  };
  
  return dfs(0, 0, 0);
}

Time: O(m n), Space: O(m n)

Pattern 3: Find All Interleavings

Generate all possible interleavings of two strings.

function findAllInterleavings(s1: string, s2: string): string[] {
  const results: string[] = [];
  
  const backtrack = (
    current: string,
    i: number,
    j: number
  ): void => {
    if (i === s1.length && j === s2.length) {
      results.push(current);
      return;
    }
    
    if (i < s1.length) {
      backtrack(current + s1[i], i + 1, j);
    }
    
    if (j < s2.length) {
      backtrack(current + s2[j], i, j + 1);
    }
  };
  
  backtrack('', 0, 0);
  return results;
}

Time: O(2^(m+n)), Space: O(m + n)

With memoization for repeated subproblems:

function findAllInterleavingsMemoized(s1: string, s2: string): string[] {
  const memo = new Map<string, string[]>();
  
  const backtrack = (i: number, j: number): string[] => {
    if (i === s1.length && j === s2.length) {
      return [''];
    }
    
    const key = `${i},${j}`;
    if (memo.has(key)) return memo.get(key)!;
    
    const results: string[] = [];
    
    if (i < s1.length) {
      const subResults = backtrack(i + 1, j);
      for (const sub of subResults) {
        results.push(s1[i] + sub);
      }
    }
    
    if (j < s2.length) {
      const subResults = backtrack(i, j + 1);
      for (const sub of subResults) {
        results.push(s2[j] + sub);
      }
    }
    
    memo.set(key, results);
    return results;
  };
  
  return backtrack(0, 0);
}

Pattern 4: Interleaving with Constraints

Interleaving with additional constraints.

Maximum consecutive characters from one string:

function isInterleaveWithMaxConsecutive(
  s1: string,
  s2: string,
  s3: string,
  maxConsecutive: number
): boolean {
  const m = s1.length;
  const n = s2.length;
  
  if (m + n !== s3.length) return false;
  
  const memo = new Map<string, boolean>();
  
  const dfs = (
    i: number,
    j: number,
    k: number,
    consecutiveFrom: 's1' | 's2' | null,
    consecutiveCount: number
  ): boolean => {
    if (k === s3.length) return true;
    
    const key = `${i},${j},${consecutiveFrom},${consecutiveCount}`;
    if (memo.has(key)) return memo.get(key)!;
    
    let result = false;
    
    if (i < m && s1[i] === s3[k]) {
      const newCount = consecutiveFrom === 's1' ? consecutiveCount + 1 : 1;
      if (newCount <= maxConsecutive) {
        result = result || dfs(i + 1, j, k + 1, 's1', newCount);
      }
    }
    
    if (j < n && s2[j] === s3[k]) {
      const newCount = consecutiveFrom === 's2' ? consecutiveCount + 1 : 1;
      if (newCount <= maxConsecutive) {
        result = result || dfs(i, j + 1, k + 1, 's2', newCount);
      }
    }
    
    memo.set(key, result);
    return result;
  };
  
  return dfs(0, 0, 0, null, 0);
}

Minimum characters from each string:

function isInterleaveWithMinChars(
  s1: string,
  s2: string,
  s3: string,
  minFromS1: number,
  minFromS2: number
): boolean {
  const m = s1.length;
  const n = s2.length;
  
  if (m + n !== s3.length) return false;
  
  const dp: boolean[][][] = Array(m + 1)
    .fill(null)
    .map(() => Array(n + 1)
      .fill(null)
      .map(() => Array(Math.max(minFromS1, minFromS2) + 1).fill(false)));
  
  dp[0][0][0] = true;
  
  for (let i = 0; i <= m; i++) {
    for (let j = 0; j <= n; j++) {
      for (let k = 0; k <= Math.max(minFromS1, minFromS2); k++) {
        if (i + j === 0) continue;
        
        if (i > 0 && s1[i - 1] === s3[i + j - 1]) {
          dp[i][j][k] = dp[i][j][k] || dp[i - 1][j][Math.max(0, k - 1)];
        }
        
        if (j > 0 && s2[j - 1] === s3[i + j - 1]) {
          dp[i][j][k] = dp[i][j][k] || dp[i][j - 1][k];
        }
      }
    }
  }
  
  return dp[m][n][minFromS1] && dp[m][n][minFromS2];
}

Pattern 5: Interleaving Count

Count number of ways to interleave two strings.

function interleaveCount(s1: string, s2: string): number {
  const m = s1.length;
  const n = s2.length;
  
  const dp: number[][] = Array(m + 1)
    .fill(null)
    .map(() => Array(n + 1).fill(0));
  
  dp[0][0] = 1;
  
  // Initialize first row
  for (let j = 1; j <= n; j++) {
    dp[0][j] = 1;
  }
  
  // Initialize first column
  for (let i = 1; i <= m; i++) {
    dp[i][0] = 1;
  }
  
  // Fill DP table
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }
  
  return dp[m][n];
}

Time: O(m n), Space: O(m n)

Using combination formula:

function interleaveCountFormula(s1: string, s2: string): number {
  const m = s1.length;
  const n = s2.length;
  
  // C(m+n, m) = (m+n)! / (m! * n!)
  return factorial(m + n) / (factorial(m) * factorial(n));
}

function factorial(n: number): number {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

Pattern 6: Interleaving with Wildcards

Handle interleaving when strings contain wildcards.

function isInterleaveWildcard(s1: string, s2: string, s3: string): boolean {
  const m = s1.length;
  const n = s2.length;
  
  if (m + n !== s3.length) return false;
  
  const dp: boolean[][] = Array(m + 1)
    .fill(null)
    .map(() => Array(n + 1).fill(false));
  
  dp[0][0] = true;
  
  // Initialize first row
  for (let j = 1; j <= n; j++) {
    const s2Char = s2[j - 1];
    const s3Char = s3[j - 1];
    dp[0][j] = dp[0][j - 1] && (s2Char === '?' || s3Char === '?' || s2Char === s3Char);
  }
  
  // Initialize first column
  for (let i = 1; i <= m; i++) {
    const s1Char = s1[i - 1];
    const s3Char = s3[i - 1];
    dp[i][0] = dp[i - 1][0] && (s1Char === '?' || s3Char === '?' || s1Char === s3Char);
  }
  
  // Fill DP table
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      const s1Char = s1[i - 1];
      const s2Char = s2[j - 1];
      const s3Char = s3[i + j - 1];
      
      const matchS1 = s1Char === '?' || s3Char === '?' || s1Char === s3Char;
      const matchS2 = s2Char === '?' || s3Char === '?' || s2Char === s3Char;
      
      dp[i][j] = 
        (dp[i - 1][j] && matchS1) ||
        (dp[i][j - 1] && matchS2);
    }
  }
  
  return dp[m][n];
}

Pattern 7: Minimum Operations to Create Interleaving

Find minimum operations to make s3 an interleaving.

function minOperationsToInterleave(
  s1: string,
  s2: string,
  s3: string
): number {
  const m = s1.length;
  const n = s2.length;
  
  if (m + n < s3.length) return -1; // Impossible
  
  const dp: number[][] = Array(m + 1)
    .fill(null)
    .map(() => Array(n + 1).fill(Infinity));
  
  dp[0][0] = 0;
  
  // Initialize first row
  for (let j = 1; j <= n; j++) {
    dp[0][j] = j; // All insertions from s2
  }
  
  // Initialize first column
  for (let i = 1; i <= m; i++) {
    dp[i][0] = i; // All insertions from s1
  }
  
  // Fill DP table
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      const k = i + j - 1;
      
      if (k < s3.length) {
        if (s1[i - 1] === s3[k]) {
          dp[i][j] = Math.min(dp[i][j], dp[i - 1][j]);
        }
        
        if (s2[j - 1] === s3[k]) {
          dp[i][j] = Math.min(dp[i][j], dp[i][j - 1]);
        }
        
        // Mismatch - need operation
        dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1, dp[i][j - 1] + 1);
      }
    }
  }
  
  return dp[m][n] === Infinity ? -1 : dp[m][n];
}

Pattern 8: Interleaving Subsequences

Check if s3 contains interleaving subsequences.

function isInterleaveSubsequence(s1: string, s2: string, s3: string): boolean {
  const m = s1.length;
  const n = s2.length;
  const k = s3.length;
  
  if (m + n > k) return false;
  
  const dp: boolean[][] = Array(m + 1)
    .fill(null)
    .map(() => Array(n + 1).fill(false));
  
  dp[0][0] = true;
  
  // Initialize first row
  for (let j = 1; j <= n; j++) {
    dp[0][j] = dp[0][j - 1] && findChar(s2[j - 1], s3, j - 1) !== -1;
  }
  
  // Initialize first column
  for (let i = 1; i <= m; i++) {
    dp[i][0] = dp[i - 1][0] && findChar(s1[i - 1], s3, i - 1) !== -1;
  }
  
  // Fill DP table
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      const pos = i + j - 1;
      
      if (pos < k) {
        dp[i][j] = 
          (dp[i - 1][j] && s1[i - 1] === s3[pos]) ||
          (dp[i][j - 1] && s2[j - 1] === s3[pos]);
      }
    }
  }
  
  return dp[m][n];
}

function findChar(char: string, s: string, start: number): number {
  for (let i = start; i < s.length; i++) {
    if (s[i] === char) return i;
  }
  return -1;
}

Pattern 9: Interleaving with Priority

Interleaving where one string has priority.

function isInterleaveWithPriority(
  s1: string,
  s2: string,
  s3: string,
  priority: 's1' | 's2'
): boolean {
  const m = s1.length;
  const n = s2.length;
  
  if (m + n !== s3.length) return false;
  
  const memo = new Map<string, boolean>();
  
  const dfs = (i: number, j: number, k: number): boolean => {
    if (k === s3.length) return true;
    
    const key = `${i},${j}`;
    if (memo.has(key)) return memo.get(key)!;
    
    let result = false;
    
    // Try priority string first
    if (priority === 's1' && i < m && s1[i] === s3[k]) {
      result = result || dfs(i + 1, j, k + 1);
    }
    
    if (priority === 's2' && j < n && s2[j] === s3[k]) {
      result = result || dfs(i, j + 1, k + 1);
    }
    
    // Then try other string
    if (priority === 's1' && j < n && s2[j] === s3[k]) {
      result = result || dfs(i, j + 1, k + 1);
    }
    
    if (priority === 's2' && i < m && s1[i] === s3[k]) {
      result = result || dfs(i + 1, j, k + 1);
    }
    
    memo.set(key, result);
    return result;
  };
  
  return dfs(0, 0, 0);
}

Pattern 10: Interleaving Validation

Validate if interleaving maintains character frequencies.

function isValidInterleaving(s1: string, s2: string, s3: string): boolean {
  if (s1.length + s2.length !== s3.length) return false;
  
  // Check character frequencies
  const freq1 = getFrequency(s1);
  const freq2 = getFrequency(s2);
  const freq3 = getFrequency(s3);
  
  // Merge frequencies from s1 and s2
  const merged = new Map<string, number>();
  for (const [char, count] of freq1) {
    merged.set(char, (merged.get(char) || 0) + count);
  }
  for (const [char, count] of freq2) {
    merged.set(char, (merged.get(char) || 0) + count);
  }
  
  // Compare with s3
  if (merged.size !== freq3.size) return false;
  
  for (const [char, count] of merged) {
    if (freq3.get(char) !== count) return false;
  }
  
  // Check if interleaving is possible
  return isInterleave(s1, s2, s3);
}

function getFrequency(s: string): Map<string, number> {
  const freq = new Map<string, number>();
  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  return freq;
}

Pattern 11: Interleaving with Replacement

Interleaving where characters can be replaced.

function isInterleaveWithReplacement(
  s1: string,
  s2: string,
  s3: string,
  maxReplacements: number
): boolean {
  const m = s1.length;
  const n = s2.length;
  
  if (m + n !== s3.length) return false;
  
  const dp: number[][] = Array(m + 1)
    .fill(null)
    .map(() => Array(n + 1).fill(Infinity));
  
  dp[0][0] = 0;
  
  // Initialize first row
  for (let j = 1; j <= n; j++) {
    dp[0][j] = s2[j - 1] === s3[j - 1] ? dp[0][j - 1] : dp[0][j - 1] + 1;
  }
  
  // Initialize first column
  for (let i = 1; i <= m; i++) {
    dp[i][0] = s1[i - 1] === s3[i - 1] ? dp[i - 1][0] : dp[i - 1][0] + 1;
  }
  
  // Fill DP table
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      const k = i + j - 1;
      
      // From s1
      const cost1 = s1[i - 1] === s3[k] ? 0 : 1;
      dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + cost1);
      
      // From s2
      const cost2 = s2[j - 1] === s3[k] ? 0 : 1;
      dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + cost2);
    }
  }
  
  return dp[m][n] <= maxReplacements;
}

Pattern 12: Interleaving Path Reconstruction

Reconstruct the actual interleaving path.

function interleavePath(s1: string, s2: string, s3: string): string[] | null {
  const m = s1.length;
  const n = s2.length;
  
  if (m + n !== s3.length) return null;
  
  const dp: boolean[][] = Array(m + 1)
    .fill(null)
    .map(() => Array(n + 1).fill(false));
  
  const parent: Array<Array<'s1' | 's2' | null>> = Array(m + 1)
    .fill(null)
    .map(() => Array(n + 1).fill(null));
  
  dp[0][0] = true;
  
  // Initialize and fill DP
  for (let j = 1; j <= n; j++) {
    if (s2[j - 1] === s3[j - 1]) {
      dp[0][j] = true;
      parent[0][j] = 's2';
    }
  }
  
  for (let i = 1; i <= m; i++) {
    if (s1[i - 1] === s3[i - 1]) {
      dp[i][0] = true;
      parent[i][0] = 's1';
    }
  }
  
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (dp[i - 1][j] && s1[i - 1] === s3[i + j - 1]) {
        dp[i][j] = true;
        parent[i][j] = 's1';
      } else if (dp[i][j - 1] && s2[j - 1] === s3[i + j - 1]) {
        dp[i][j] = true;
        parent[i][j] = 's2';
      }
    }
  }
  
  if (!dp[m][n]) return null;
  
  // Reconstruct path
  const path: string[] = [];
  let i = m, j = n;
  
  while (i > 0 || j > 0) {
    if (parent[i][j] === 's1') {
      path.unshift(`s1[${i - 1}]=${s1[i - 1]}`);
      i--;
    } else if (parent[i][j] === 's2') {
      path.unshift(`s2[${j - 1}]=${s2[j - 1]}`);
      j--;
    } else {
      break;
    }
  }
  
  return path;
}

When to Use Interleaving Techniques

Use interleaving algorithms when:

  • Problem mentions "interleave", "interweave", or "merge"
  • Need to check if string is interleaving
  • Maintain order from both strings
  • Find all combinations of interleaving
  • Handle constraints on interleaving
  • Optimize with DP or memoization

Template (DP-based)

function isInterleaveTemplate(s1: string, s2: string, s3: string): boolean {
  const m = s1.length;
  const n = s2.length;
  
  if (m + n !== s3.length) return false;
  
  const dp: boolean[][] = Array(m + 1)
    .fill(null)
    .map(() => Array(n + 1).fill(false));
  
  dp[0][0] = true;
  
  // Initialize boundaries
  // Fill DP table
  
  return dp[m][n];
}

Template (Recursive with Memo)

function isInterleaveRecursiveTemplate(s1: string, s2: string, s3: string): boolean {
  const memo = new Map<string, boolean>();
  
  const dfs = (i: number, j: number, k: number): boolean => {
    if (k === s3.length) return true;
    
    const key = `${i},${j}`;
    if (memo.has(key)) return memo.get(key)!;
    
    let result = false;
    
    if (i < s1.length && s1[i] === s3[k]) {
      result = result || dfs(i + 1, j, k + 1);
    }
    
    if (j < s2.length && s2[j] === s3[k]) {
      result = result || dfs(i, j + 1, k + 1);
    }
    
    memo.set(key, result);
    return result;
  };
  
  return dfs(0, 0, 0);
}

Time and Space Complexity Summary

  • Basic interleaving: O(m n) time, O(m n) space, O(min(m, n)) optimized
  • All interleavings: O(2^(m+n)) time, O(m + n) space
  • With constraints: O(m n k) time where k is constraint parameter
  • Count: O(m n) time, O(m n) space
  • Path reconstruction: O(m n) time, O(m n) space

Practice Tips

  1. Use DP — For checking if interleaving is possible
  2. Use backtracking — For finding all combinations
  3. Memoization — Essential for recursive solutions
  4. Space optimization — Use 1D DP when possible
  5. Handle edge cases — Empty strings, length mismatch
  6. State transitions — Track indices carefully

Common Mistakes

  1. Index errors — Careful with i+j-1 for s3 index
  2. Not initializing — First row and column
  3. Wrong state — dp[i][j] represents using i chars from s1, j from s2
  4. Missing memoization — Causes TLE in recursion
  5. Length check — Always verify m + n === s3.length first

Related Concepts

  • Dynamic Programming — Core technique for interleaving
  • String Manipulation — Basic string operations
  • Backtracking — For finding all combinations
  • Edit Distance — Similar DP structure

String interleaving problems are common in interviews. Master these patterns, and you'll be well-prepared for string combination and DP-related questions.

← PreviousWord Break Problems
Next →—