Interleaving String
Interleaving String is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 2D Array (Unique Paths on Grid) subpattern.
- NeetCode 150 · #116 of 150 · 2-D Dynamic Programming
- NeetCode 250 · #199 of 250 · 2-D Dynamic Programming
Problem statement
Given three strings s1, s2, and s3, determine whether s3 can be formed by interleaving s1 and s2. An interleaving preserves the left-to-right order of the characters taken from s1 and separately preserves the order of the characters taken from s2; at each position, the next character comes from one of those two strings.
Every character from both s1 and s2 must be used exactly once, so a valid interleaving must also have the combined length of the two source strings. Return true if at least one valid interleaving produces s3; otherwise, return false.
Example 1:
Input: s1 = "cat", s2 = "dog", s3 = "cdoatg" Output: true Explanation: The characters can be taken in order as c from s1, d and o from s2, a and t from s1, and g from s2.
Example 2:
Input: s1 = "ab", s2 = "ba", s3 = "bbaa" Output: false Explanation: After taking b from s2, the next b cannot come from either string: s2 must continue with a, while s1 begins with a.
Example 3:
Input: s1 = "", s2 = "hello", s3 = "hello" Output: true Explanation: When s1 is empty, the only possible interleaving uses all of s2, which exactly matches s3.
Constraints:
- 0 <= s1.length <= 100 - 0 <= s2.length <= 100 - 0 <= s3.length <= 200 - s1, s2, and s3 contain only lowercase English letters - s3.length = s1.length + s2.length
Topics and companies
Topics: Dynamic Programming, String, Memoization.
How to practise Interleaving String on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(s1.length * s2.length) time and O(s2.length) space.
Open Interleaving String in the code editor, or read the Interleaving String editorial for a worked solution with its approach and complexity analysis.
Where Interleaving String sits in the DSA pattern sheet
- Dynamic Programming (DP) Patterns pattern guide
- 2D Array (Unique Paths on Grid) subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Interleaving String
Other problems that use the same 2D Array (Unique Paths on Grid) and Dynamic Programming (DP) Patterns techniques:
- Count Square Submatrices with All Ones — Medium, same subpattern
- Longest Increasing Path in a Matrix — Hard, same subpattern
- Maximal Square — Medium, same subpattern
- Minimum Falling Path Sum — Medium, same subpattern
- Minimum Path Sum — Medium, same subpattern
- Triangle — Medium, same subpattern