Search⌘ K
Home
Courses
Grokking Dynamic Programming Interview in Python

Interleaving Strings

Explore how to verify if one string is formed by interleaving two others through dynamic programming. Learn to implement both top-down and bottom-up approaches, understand the key principles of optimal substructure and overlapping subproblems, and optimize the solution from naive recursion to efficient DP methods.

We'll cover the following...

Statement

Given strings s1, s2, and s3, find whether an interleaving of s1 and s2 forms s3.

An interleaving of two strings a and b is a configuration where a and b splits into nn and mm substrings, respectively, such that:

  • a =a1= a_{1} + a2a_{2} + … + ana_{n}
  • b =b1= b_{1} + b2b_{2} + … + bmb_{m}
  • ∣n−m∣⩽1\left | n - m \right | \leqslant 1
  • The interleaving can follow either of the following two formats:
    • a1+b1+a2+b2+a3+b3+...a_{1} + b_{1} + a_{2} + b_{2} + a_{3} + b_{3} + ...
...