Print All Interleavings Of Given Two Strings In C++

In this guide, we will explore the process of displaying all interleavings of two specified strings in C++. However, prior to delving into the implementation details, it's essential to understand the concept of interleavings.

What are Interleavings?

Combining two strings to create interleavings involves merging their characters in various sequences while preserving the original order of characters. For instance, when interleaving "AB" and "CD", the resulting combinations are "ABCD", "ACBD", "ACDB", "CABD", "CADB", and "CDAB".

Solving the task of generating all potential interleavings of two specified strings is a frequently encountered challenge in the realms of recursion and dynamic programming.

Problem Statement

Generate and display all potential interleavings of two strings, str1 and str2. When strings are interleaved, the sequence of characters from each string is maintained.

For example:

str1 = "AB"

str2 = "CD"

Possible Interleavings:

1. Naive Recursive Approach

A straightforward recursive approach involves creating interleavings by selecting a character from either string in each iteration. When str1 is not empty, the process entails recursively generating interleavings for str1[1...] and str2, then adding str1[0] to the beginning of the result. Similarly, when str2 is not empty, interleavings are generated recursively for str1 and str2[1...], and str2[0] is added to the start of the result.

Base scenarios:

• ✅ In the event that both strings are void of content, display the interleaving that has been produced.
• ✅ If one of the strings is devoid of characters, select only from the non-empty string when creating the interleaving.

It results in an exponential time complexity of O(2^n), where n represents the size of the two strings.

Example:

Let's consider an example to display all possible interleavings of two specified strings in the C++ programming language.

#include <iostream>
using namespace std;

// Recursive Function to print interleavings 
void interleave(string s1, string s2, string res) {

 // Base cases
 if (s1.empty() && s2.empty()) {
 cout << res << endl;
 return; 
 }
 
 if (!s1.empty()) {
 interleave(s1.substr(1), s2, res + s1[0]); 
 }
 
 if (!s2.empty()) {
 interleave(s1, s2.substr(1), res + s2[0]);
 }
}

int main() {

 string str1 = "AB";
 string str2 = "CD";
 
 interleave(str1, str2, "");

 return 0;
}

Output:

ABCD
ACBD
ACDB
CABD
CADB
CDAB

This function iteratively produces all legitimate intermixes in lexicographical sequence.

2. Dynamic Programming Approach

We can optimize it using a bottom-up dynamic programming approach.

• ✅ Create a 2D matrix dpm+1 to store the interleavings.
• ✅ Fill up the matrix diagonally from empty strings to full strings.
• ✅ To fill a cell dpi: Appendstr1[i-1] to interleavings of dpi-1 Appendstr2[j-1] to interleavings of dpi
• ✅ Final interleavings will be stored in dpm.
• ✅ It reduces the complexity to O(m*n) as we store the results instead of recomputing.
• ✅ Appendstr1[i-1] to interleavings of dpi-1
• ✅ Appendstr2[j-1] to interleavings of dpi

Example:

Implementing Dynamic Programming Approach in C++:

Below is a sample C++ code demonstrating the application of dynamic programming technique:

#include <iostream>
using namespace std;

int fibonacci(int n) {
    int fib[n + 1];
    fib[0] = 0;
    fib[1] = 1;

    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }

    return fib[n];
}

int main() {
    int n = 10;
    cout << "Fibonacci number at position " << n << " is: " << fibonacci(n) << endl;
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

//Function to print interleavings using DP
void printInterleavings(string s1, string s2){
 
 int m = s1.length();
 int n = s2.length();
 
 // dp table to store interleavings
 vector<vector<vector<string>>> dp(m+1, vector<vector<string>>(n+1)); 
 
 // Base cases
 for(int i=0; i<=m; i++){
 dp[i][0] = {s1.substr(0, i)}; 
 }
 
 for(int j=0; j<=n; j++){
 dp[0][j] = {s2.substr(0, j)};
 }

 // Build interleavings from smaller to larger strings 
 for(int i=1; i<=m; i++){
 for(int j=1; j<=n; j++){
 
 // Append s1[i-1] to previous interleavings
 for(string s: dp[i-1][j]){
 s.push_back(s1[i-1]);
 dp[i][j].push_back(s);
 }
 
 // Append s2[j-1] to previous interleavings 
 for(string s: dp[i][j-1]){
 s.push_back(s2[j-1]);
 dp[i][j].push_back(s);
 }
 }
 }
 
 // Print all interleavings
 for(string s: dp[m][n]){
 cout << s << "\n";
 }
}

int main() {

 string s1 = "AB";
 string s2 = "CD";

 printInterleavings(s1, s2);

 return 0;
}

Output:

ABCD
ACBD
ACDB 
CABD
CADB
CDAB

This DP technique starting from the bottom enhances performance by preventing redundant calculations, making it more efficient compared to the recursive method.