Interleaving String: A Dynamic Programming Challenge

Given three strings, determine if the third string can be formed by interleaving the characters of the first two strings while maintaining the relative order of characters within each of the first two strings. This is a classic problem that tests your ability to think about string manipulation and often leads to dynamic programming solutions.

Problem Description

You are provided with three strings: s1, s2, and s3. Your task is to write a function that returns true if s3 is formed by interleaving the characters of s1 and s2. Interleaving means that all characters from s1 and s2 must be present in s3, and the order of characters within s1 must be preserved, and the order of characters within s2 must also be preserved.

Key Requirements:

• The function must accept three strings: s1, s2, and s3.
• The function must return a boolean value: true if s3 is an interleaving of s1 and s2, false otherwise.
• The lengths of s1 and s2 combined must equal the length of s3. If they don't, s3 cannot possibly be an interleaving.

Expected Behavior:

• If s3 can be formed by taking characters from s1 and s2 in their original order, then return true.
• If at any point it's impossible to form s3 by picking characters from s1 or s2 while respecting their internal order, return false.

Edge Cases to Consider:

• Empty strings for s1, s2, or s3.
• s1 or s2 being empty while the other is not.
• s1, s2, and s3 having duplicate characters.

Examples

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation:
s3 can be formed by interleaving s1 and s2 like this:
s1: a a b c c
s2:   d b b c a
s3: a a d b b c b c a

The characters of s1 are used in order: 'a', 'a', 'b', 'c', 'c'.
The characters of s2 are used in order: 'd', 'b', 'b', 'c', 'a'.

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Explanation:
The character 'b' appears too many times in s3 compared to the combined occurrences in s1 and s2.
Alternatively, tracing the path would show a mismatch at some point.

Example 3:

Input: s1 = "", s2 = "", s3 = ""
Output: true
Explanation:
An empty string can be formed by interleaving two empty strings.

Example 4:

Input: s1 = "a", s2 = "b", s3 = "ab"
Output: true
Explanation: s3 is formed by s1 then s2.

Example 5:

Input: s1 = "a", s2 = "b", s3 = "ba"
Output: true
Explanation: s3 is formed by s2 then s1.

Constraints

• 0 <= s1.length, s2.length, s3.length <= 100
• s1, s2, and s3 consist of lowercase English letters.
• The combined length of s1 and s2 must equal the length of s3 for s3 to be a valid interleaving. (This is often an implicit constraint, but it's good to be aware of).
• You should aim for an efficient solution, ideally with a time complexity better than exponential.

Notes

Consider how you can build up a solution for larger strings based on solutions for smaller substrings. Think about the state you need to keep track of at each step. A common approach involves dynamic programming or recursion with memoization. What are the subproblems you can identify?