Interleaving String

The problem

Decide whether s3 is an interleaving of s1 and s2: it must use every letter of s1 and every letter of s2 exactly once and nothing else, with the letters of s1 in their original order and the letters of s2 in theirs. The two strings may be mixed in any way. Return true if s3 is such an interleaving and false if not. Any of the strings may be empty, and two empty strings interleave into the empty string.

What to write

function solve(s1: string, s2: string, s3: string): boolean

Input
s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbcbcac"

Output
true

Input
s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbbaccc"

Output
false

Constraints

Each source has at most 100 characters and may be empty.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Every letter of s1 and of s2 is used exactly once, so their lengths must add up to the length of s3. If they do not, the answer is false before you compare a single letter. An empty string is allowed and adds nothing.

2. Hint 2: Ask a smaller question

   Build s3 from left to right with s1 = "ab", s2 = "ac" and s3 = "acab". The first a could come from either string. Follow both choices by hand. What is the least you must remember about your progress to continue, and does the order of earlier picks matter?

3. Hint 3: Name the pattern

   Your progress is two numbers: how many letters of s1 and how many of s2 are used. Together they also say how much of s3 is built. Each pair of counts either works or not, and that depends only on pairs with one letter fewer. A table over two counts is two-dimensional dynamic programming. Read the lesson on two-dimensional dynamic programming.

4. Hint 4: State the invariant

   Keep one row, a slot for each count j of s2 letters. After the pass for the first i letters of s1, slot j says whether they and the first j letters of s2 can be interleaved into the first i + j letters of s3. Until a slot is rewritten, it still holds the answer from the pass before.

5. Hint 5: Sketch the pseudocode

   Lengths must add up, else false. Row of false slots, slot[0]=true. For i from 0 to the length of s1, then j from 0 to the length of s2, skipping i=j=0: c = s3[i+j-1], counting positions from 0. slot[j] = (i>0 and slot[j] and s1[i-1] is c) or (j>0 and slot[j-1] and s2[j-1] is c). Return the last slot.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

A prefix of the target ends with a matching character from either source. Use a row-compressed DP over consumed source lengths.

The slow way

Walk along s3. For each letter, try taking it from s1 if the next letter of s1 matches, and try s2 the same way. When both match you must follow both branches, because one of them can get stuck later. With many ties the branches multiply: when s1 and s2 are twelve a's each and s3 is 23 a's and then a b, this takes 7696443 calls.

The insight

The order in which earlier letters were taken does not matter. Only two counts matter: how many letters of s1 and how many of s2 are used. They tell you what comes next in all three strings. There are only (length of s1 + 1) × (length of s2 + 1) pairs of counts, so each pair is answered once and reused: that is dynamic programming.

Step by step

1. If the lengths do not add up to the length of s3, the answer is false. Every letter of s1 and s2 must be used exactly once and nothing else may appear. So s3 must be exactly as long as the two together. The check also keeps the loops from reading past the end of s3.
2. Keep a row of answers per count of s2 letters; count 0 starts true. Slot j will say whether the letters taken so far from s1 and the first j letters of s2 can be interleaved into the start of s3. Taking nothing from either gives the empty start, so slot 0 begins true.
3. Go through every pair of counts, row by row, except the pair 0 and 0. Each pass of the outer loop stands for one more letter of s1, starting from none, and rewrites the slots from left to right. The pair 0 and 0 is skipped because its answer, true, is already in slot 0.
4. Last letter from s1: needs a true slot above and equal letters. Until it is rewritten, slot j holds the answer for one letter fewer of s1: the slot above in a full table. That answer must be true, and the newest letter of s1 must be the letter s3 needs.
5. Last letter from s2: needs a true slot on the left and equal letters. The slot on the left already belongs to this row: the same letters of s1 and one letter fewer of s2. It must be true, and the newest letter of s2 must be the letter s3 needs.
6. The slot is true when at least one of the two ways works. The last letter of the piece of s3 came from s1 or from s2; there is no third source. If neither way works the slot becomes false, even if it was true for the row above.
7. Return the last slot: every letter of s1 and of s2 is used. After the final pass the row stands for all of s1, and its last slot for all of s2 as well. Together they must build all of s3, which is the question asked.

The same numbered steps are the comments in each solution.

function solve(s1, s2, s3) {
  // 1. If the lengths do not add up to the length of s3, the answer is false
  if (s1.length + s2.length !== s3.length) return false;
  // 2. Keep a row of answers per count of s2 letters; count 0 starts true
  const dp = Array(s2.length + 1).fill(false);
  dp[0] = true;
  // 3. Go through every pair of counts, row by row, except the pair 0 and 0
  for (let i = 0; i <= s1.length; i++)
    for (let j = 0; j <= s2.length; j++) {
      if (i === 0 && j === 0) continue;
      // 4. Last letter from s1: needs a true slot above and equal letters
      const fromS1 = i > 0 && dp[j] && s1[i - 1] === s3[i + j - 1];
      // 5. Last letter from s2: needs a true slot on the left and equal letters
      const fromS2 = j > 0 && dp[j - 1] && s2[j - 1] === s3[i + j - 1];
      // 6. The slot is true when at least one of the two ways works
      dp[j] = fromS1 || fromS2;
    }
  // 7. Return the last slot: every letter of s1 and of s2 is used
  return dp[s2.length];
}

function solve(s1: string, s2: string, s3: string): boolean {
  // 1. If the lengths do not add up to the length of s3, the answer is false
  if (s1.length + s2.length !== s3.length) return false;
  // 2. Keep a row of answers per count of s2 letters; count 0 starts true
  const dp = Array(s2.length + 1).fill(false);
  dp[0] = true;
  // 3. Go through every pair of counts, row by row, except the pair 0 and 0
  for (let i = 0; i <= s1.length; i++)
    for (let j = 0; j <= s2.length; j++) {
      if (i === 0 && j === 0) continue;
      // 4. Last letter from s1: needs a true slot above and equal letters
      const fromS1 = i > 0 && dp[j] && s1[i - 1] === s3[i + j - 1];
      // 5. Last letter from s2: needs a true slot on the left and equal letters
      const fromS2 = j > 0 && dp[j - 1] && s2[j - 1] === s3[i + j - 1];
      // 6. The slot is true when at least one of the two ways works
      dp[j] = fromS1 || fromS2;
    }
  // 7. Return the last slot: every letter of s1 and of s2 is used
  return dp[s2.length];
}

def solve(s1, s2, s3):
    # 1. If the lengths do not add up to the length of s3, the answer is false
    if len(s1) + len(s2) != len(s3):
        return False
    # 2. Keep a row of answers per count of s2 letters; count 0 starts true
    dp = [False] * (len(s2) + 1)
    dp[0] = True
    # 3. Go through every pair of counts, row by row, except the pair 0 and 0
    for i in range(len(s1) + 1):
        for j in range(len(s2) + 1):
            if i == 0 and j == 0:
                continue
            # 4. Last letter from s1: needs a true slot above and equal letters
            from_s1 = i > 0 and dp[j] and s1[i - 1] == s3[i + j - 1]
            # 5. Last letter from s2: needs a true slot on the left and equal letters
            from_s2 = j > 0 and dp[j - 1] and s2[j - 1] == s3[i + j - 1]
            # 6. The slot is true when at least one of the two ways works
            dp[j] = from_s1 or from_s2
    # 7. Return the last slot: every letter of s1 and of s2 is used
    return dp[len(s2)]

Example 1, traced

Input
s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbcbcac"

Output
true

Why it works

Slot j of the row for i letters says whether the first i letters of s1 and the first j of s2 can be interleaved into the first i + j letters of s3. The last letter of such a piece comes from s1 or from s2, and what is left is a smaller piece with one letter fewer. Both smaller answers are computed first.

Time and space

Time O(m n), extra space O(n). With m and n the lengths of s1 and s2, there are (m + 1) × (n + 1) pairs of counts, each handled with a few comparisons, so the time is O(m n). Only one row of n + 1 answers is kept, so the space is O(n).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Taking each letter from s1 whenever it fits, and from s2 only otherwise, fails: an early pick can block a later one. Example 1 comes out false that way. When both strings fit, both choices must stay open.
• Slot 0 needs an update in every pass too. Starting the inner loop at slot 1 leaves slot 0 true forever, as if s1 alone always matched s3: s1 = "a", empty s2 and s3 = "c" would give true.
• Keep the length check. Without it, s1 = "a", s2 = "b" and s3 = "abc" comes out true, because the loops never look at the extra c.

Pattern

Two-dimensional dynamic programming. Builds on Unique Paths and Longest Common Subsequence.

Keep going