Interleaving String
Understanding the Problem of Interleaving Strings
String manipulation is a cornerstone of problem-solving in programming. Among the many fascinating challenges, the Interleaving String Problem offers an interesting test of logical thinking and algorithmic design.
In this article, we will break down this problem, understand what interleaving means, and explore how to determine whether one string can be formed by interleaving two other strings.
Problem Description
Imagine you are given three strings: s1, s2, and s3. Your goal is to determine whether the third string, s3, can be created by combining the characters of s1 and s2 in an interleaved fashion. You should return true if it’s possible to interleave the strings to form s3, or false otherwise.
What Does Interleaving Mean?
Interleaving two strings involves taking their characters alternately to form a new string. However, there are a few rules to follow:
Balanced Partitions: Divide the strings
s1ands2into substrings such that the difference in the number of substrings between them is at most 1.- If
s1is split intonsubstrings ands2intomsubstrings, then the condition|n - m| <= 1must hold.
- If
Order Preservation: The order of characters in
s1ands2should remain the same in the final string.- For example, given
s1 = "abc"ands2 = "def", a valid interleaved string could be"adbcef"or"abdecf", but not"acbdef".
- For example, given
Valid Interleaving Structure: The final interleaved string alternates parts of
s1ands2. Examples of interleaving include:s1 + t1 + s2 + t2 + ...- Or
t1 + s1 + t2 + s2 + ...
Why Is This Problem Useful?
This problem is a great exercise for mastering:
- Dynamic Programming: Efficiently solving subproblems that require decision-making between choices.
- String Manipulation: Understanding how to handle character sequences and their relationships.
- Logical Thinking: Designing a solution while keeping track of multiple constraints.
Example 1
Input: s1 = "aaaa", s2 = "bbbb", s3 = "aabbbbaa"
Output: true
Explanation:
We can split s1 into ["aa", "aa"], s2 can remain as "bbbb" and s3 is formed by interleaving ["aa", "aa"] and "bbbb".
Example 2
Input: s1 = "abc", s2 = "xyz", s3 = "abxzcy"
Output: false
Example 3
Input: s1 = "abc", s2 = "xyz", s3 = "abxzcy"
Output: false
Explanation:
We can’t split s3 into ["ab", "xz", "cy"] as the order of characters is not maintained.
Approaching the Solution
To solve the interleaving string problem, one might consider using a dynamic programming or recursive approach to evaluate all possible ways to combine the strings. The solution must ensure that all conditions for interleaving are satisfied at every step.
There are mainly Four approach to solve this problem –
- Recursion
- Dynamic Programming (Top-Down)
- Dynamic Programming (Bottom-up)
- Dynamic Programming (Space Optimized)
1.Recursion
- Time complexity: O(n∗2n)
- Space complexity: O(n∗2n)
Python
C++
Java
JavaScript
Python
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
def dfs(i, j, k):
if k == len(s3):
return (i == len(s1)) and (j == len(s2))
if i < len(s1) and s1[i] == s3[k]:
if dfs(i + 1, j, k + 1):
return True
if j < len(s2) and s2[j] == s3[k]:
if dfs(i, j + 1, k + 1):
return True
return False
return dfs(0, 0, 0)C++
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
return dfs(0, 0, 0, s1, s2, s3);
}
bool dfs(int i, int j, int k, string& s1, string& s2, string& s3) {
if (k == s3.length()) {
return (i == s1.length()) && (j == s2.length());
}
if (i < s1.length() && s1[i] == s3[k]) {
if (dfs(i + 1, j, k + 1, s1, s2, s3)) {
return true;
}
}
if (j < s2.length() && s2[j] == s3[k]) {
if (dfs(i, j + 1, k + 1, s1, s2, s3)) {
return true;
}
}
return false;
}
};Java
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
return dfs(0, 0, 0, s1, s2, s3);
}
private boolean dfs(int i, int j, int k, String s1, String s2, String s3) {
if (k == s3.length()) {
return (i == s1.length()) && (j == s2.length());
}
if (i < s1.length() && s1.charAt(i) == s3.charAt(k)) {
if (dfs(i + 1, j, k + 1, s1, s2, s3)) {
return true;
}
}
if (j < s2.length() && s2.charAt(j) == s3.charAt(k)) {
if (dfs(i, j + 1, k + 1, s1, s2, s3)) {
return true;
}
}
return false;
}
}JavaScript
class Solution {
/**
* @param {string} s1
* @param {string} s2
* @param {string} s3
* @return {boolean}
*/
isInterleave(s1, s2, s3) {
const dfs = (i, j, k) => {
if (k === s3.length) {
return (i === s1.length) && (j === s2.length);
}
if (i < s1.length && s1[i] === s3[k]) {
if (dfs(i + 1, j, k + 1)) {
return true;
}
}
if (j < s2.length && s2[j] === s3[k]) {
if (dfs(i, j + 1, k + 1)) {
return true;
}
}
return false;
}
return dfs(0, 0, 0);
}
}2. Dynamic Programming (Top-Down)
Time & Space Complexity
- Time complexity: O(2^m+n)
- Space complexity: O(m+n)
Python
Java
C++
JavaScript
Python
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
if len(s1) + len(s2) != len(s3):
return False
dp = [[False] * (len(s2) + 1) for i in range(len(s1) + 1)]
dp[len(s1)][len(s2)] = True
for i in range(len(s1), -1, -1):
for j in range(len(s2), -1, -1):
if i < len(s1) and s1[i] == s3[i + j] and dp[i + 1][j]:
dp[i][j] = True
if j < len(s2) and s2[j] == s3[i + j] and dp[i][j + 1]:
dp[i][j] = True
return dp[0][0]Java
public class Solution {
private Boolean[][] dp;
public boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length(), n = s2.length();
if (m + n != s3.length()) return false;
dp = new Boolean[m + 1][n + 1];
return dfs(0, 0, 0, s1, s2, s3);
}
private boolean dfs(int i, int j, int k, String s1, String s2, String s3) {
if (k == s3.length()) {
return (i == s1.length()) && (j == s2.length());
}
if (dp[i][j] != null) {
return dp[i][j];
}
boolean res = false;
if (i < s1.length() && s1.charAt(i) == s3.charAt(k)) {
res = dfs(i + 1, j, k + 1, s1, s2, s3);
}
if (!res && j < s2.length() && s2.charAt(j) == s3.charAt(k)) {
res = dfs(i, j + 1, k + 1, s1, s2, s3);
}
dp[i][j] = res;
return res;
}
}
C++
class Solution {
vector> dp;
public:
bool isInterleave(string s1, string s2, string s3) {
int m = s1.length(), n = s2.length();
if (m + n != s3.length()) return false;
dp = vector>(m + 1, vector(n + 1, -1));
return dfs(0, 0, 0, s1, s2, s3);
}
bool dfs(int i, int j, int k, string& s1, string& s2, string& s3) {
if (k == s3.length()) {
return (i == s1.length()) && (j == s2.length());
}
if (dp[i][j] != -1) {
return dp[i][j];
}
bool res = false;
if (i < s1.length() && s1[i] == s3[k]) {
res = dfs(i + 1, j, k + 1, s1, s2, s3);
}
if (!res && j < s2.length() && s2[j] == s3[k]) {
res = dfs(i, j + 1, k + 1, s1, s2, s3);
}
dp[i][j] = res;
return res;
}
}; JavaScript
class Solution {
/**
* @param {string} s1
* @param {string} s2
* @param {string} s3
* @return {boolean}
*/
isInterleave(s1, s2, s3) {
const m = s1.length, n = s2.length;
if (m + n !== s3.length) return false;
const dp = Array.from({ length: m + 1 }, () =>
Array(n + 1).fill(-1));
const dfs = (i, j, k) => {
if (k === s3.length) {
return (i === s1.length) && (j === s2.length);
}
if (dp[i][j] !== -1) {
return dp[i][j];
}
let res = false;
if (i < s1.length && s1[i] === s3[k]) {
res = dfs(i + 1, j, k + 1);
}
if (!res && j < s2.length && s2[j] === s3[k]) {
res = dfs(i, j + 1, k + 1);
}
dp[i][j] = res;
return res;
}
return dfs(0, 0, 0);
}
}3. Dynamic Programming (Bottom-Up)
Time & Space Complexity
- Time complexity: O(m∗n)
- Space complexity: O(m∗n)
Python
Java
C++
JavaScript
Python
class Solution:
def maxCoins(self, nums):
n = len(nums)
new_nums = [1] + nums + [1]
dp = [[0] * (n + 2) for _ in range(n + 2)]
for l in range(n, 0, -1):
for r in range(l, n + 1):
for i in range(l, r + 1):
coins = new_nums[l - 1] * new_nums[i] * new_nums[r + 1]
coins += dp[l][i - 1] + dp[i + 1][r]
dp[l][r] = max(dp[l][r], coins)
return dp[1][n]Java
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length(), n = s2.length();
if (m + n != s3.length()) {
return false;
}
boolean[][] dp = new boolean[m + 1][n + 1];
dp[m][n] = true;
for (int i = m; i >= 0; i--) {
for (int j = n; j >= 0; j--) {
if (i < m && s1.charAt(i) == s3.charAt(i + j) && dp[i + 1][j]) {
dp[i][j] = true;
}
if (j < n && s2.charAt(j) == s3.charAt(i + j) && dp[i][j + 1]) {
dp[i][j] = true;
}
}
}
return dp[0][0];
}
}
C++
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int m = s1.length(), n = s2.length();
if (m + n != s3.length()) {
return false;
}
vector> dp(m + 1, vector(n + 1, false));
dp[m][n] = true;
for (int i = m; i >= 0; i--) {
for (int j = n; j >= 0; j--) {
if (i < m && s1[i] == s3[i + j] && dp[i + 1][j]) {
dp[i][j] = true;
}
if (j < n && s2[j] == s3[i + j] && dp[i][j + 1]) {
dp[i][j] = true;
}
}
}
return dp[0][0];
}
}; JavaScript
class Solution {
/**
* @param {string} s1
* @param {string} s2
* @param {string} s3
* @return {boolean}
*/
isInterleave(s1, s2, s3) {
let m = s1.length, n = s2.length;
if (m + n !== s3.length) {
return false;
}
const dp = Array.from({ length: m + 1 }, () =>
Array(n + 1).fill(false));
dp[m][n] = true;
for (let i = m; i >= 0; i--) {
for (let j = n; j >= 0; j--) {
if (i < m && s1[i] === s3[i + j] && dp[i + 1][j]) {
dp[i][j] = true;
}
if (j < n && s2[j] === s3[i + j] && dp[i][j + 1]) {
dp[i][j] = true;
}
}
}
return dp[0][0];
}
}4. Dynamic Programming (Space Optimized)
Time & Space Complexity
- Time complexity: O(m∗n)
- Space complexity: O(min(m,n))
Python
Java
C++
JavaScript
Python
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
m, n = len(s1), len(s2)
if m + n != len(s3):
return False
if n < m:
s1, s2 = s2, s1
m, n = n, m
dp = [False for _ in range(n + 1)]
dp[n] = True
for i in range(m, -1, -1):
nextDp = [False for _ in range(n + 1)]
nextDp[n] = True
for j in range(n, -1, -1):
if i < m and s1[i] == s3[i + j] and dp[j]:
nextDp[j] = True
if j < n and s2[j] == s3[i + j] and nextDp[j + 1]:
nextDp[j] = True
dp = nextDp
return dp[0]Java
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length(), n = s2.length();
if (m + n != s3.length()) return false;
if (n < m) {
String temp = s1;
s1 = s2;
s2 = temp;
int tempLength = m;
m = n;
n = tempLength;
}
boolean[] dp = new boolean[n + 1];
dp[n] = true;
for (int i = m; i >= 0; i--) {
boolean[] nextDp = new boolean[n + 1];
nextDp[n] = true;
for (int j = n; j >= 0; j--) {
if (i < m && s1.charAt(i) == s3.charAt(i + j) && dp[j]) {
nextDp[j] = true;
}
if (j < n && s2.charAt(j) == s3.charAt(i + j) && nextDp[j + 1]) {
nextDp[j] = true;
}
}
dp = nextDp;
}
return dp[0];
}
}
C++
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int m = s1.size(), n = s2.size();
if (m + n != s3.size()) return false;
if (n < m) {
swap(s1, s2);
swap(m, n);
}
vector dp(n + 1);
dp[n] = true;
for (int i = m; i >= 0; --i) {
vector nextDp(n + 1);
nextDp[n] = true;
for (int j = n; j >= 0; --j) {
if (i < m && s1[i] == s3[i + j] && dp[j]) {
nextDp[j] = true;
}
if (j < n && s2[j] == s3[i + j] && nextDp[j + 1]) {
nextDp[j] = true;
}
}
dp = nextDp;
}
return dp[0];
}
}; JavaScript
class Solution {
/**
* @param {string} s1
* @param {string} s2
* @param {string} s3
* @return {boolean}
*/
isInterleave(s1, s2, s3) {
let m = s1.length, n = s2.length;
if (m + n !== s3.length) return false;
if (n < m) {
[s1, s2] = [s2, s1];
[m, n] = [n, m];
}
let dp = Array(n + 1).fill(false);
dp[n] = true;
for (let i = m; i >= 0; i--) {
let nextDp = Array(n + 1).fill(false);
nextDp[n] = true;
for (let j = n; j >= 0; j--) {
if (i < m && s1[i] === s3[i + j] && dp[j]) {
nextDp[j] = true;
}
if (j < n && s2[j] === s3[i + j] && nextDp[j + 1]) {
nextDp[j] = true;
}
}
dp = nextDp;
}
return dp[0];
}
}Conclusion
The Interleaving String problem is more than just a test of string manipulation skills; it’s a practical exercise in algorithmic thinking. It demonstrates the power of logical sequencing and helps build a strong foundation for solving real-world problems where multiple sequences or inputs need to be merged in specific ways.
By tackling problems like this, you sharpen your ability to think critically and design efficient solutions for complex challenges.
