Inter leaving String - C++ Solution

1. Introduction

This blog post addresses a fascinating problem in string manipulation, commonly known as string interleaving. The task involves generating all possible interleavings of two given strings, ensuring that the order of characters in each string is preserved.

Problem

Given two strings, the objective is to find all the possible interleavings that can be formed using all characters from both strings. An interleaving of two strings maintains the order of characters as they appear in the original strings.

2. Solution Steps

1. Use a recursive function to generate interleavings.

2. At each step, choose a character either from the first or the second string and append it to the current interleaving.

3. Ensure that the order of characters in the individual strings is preserved.

4. Once both strings are exhausted, add the generated interleaving to a set or list.

5. Backtrack to explore all possible combinations.

3. Code Program

#include <iostream>
#include <string>
#include <set>
using namespace std;

// Recursive function to generate interleavings
void generateInterleavings(string res, string X, string Y, set<string>& interleavings) {
    // If both strings are empty, add result to the set
    if (X.empty() && Y.empty()) {
        interleavings.insert(res);
        return;
    }

    // If string X is not empty, append its first character and recurse
    if (!X.empty()) {
        generateInterleavings(res + X[0], X.substr(1), Y, interleavings);
    }

    // If string Y is not empty, append its first character and recurse
    if (!Y.empty()) {
        generateInterleavings(res + Y[0], Y, X.substr(1), interleavings);
    }
}

// Function to find all interleavings of X and Y
set<string> findAllInterleavings(const string& X, const string& Y) {
    set<string> interleavings;
    generateInterleavings("", X, Y, interleavings);
    return interleavings;
}

int main() {
    string X = "ABC", Y = "ACB";
    set<string> result = findAllInterleavings(X, Y);

    cout << "Interleavings: ";
    for (const string& str : result) {
        cout << str << " ";
    }
    cout << endl;

    return 0;
}

Output:

Interleavings: AACBBC AACBCB AABCCB ABACCB ABACBC ACABBC ACABCB ACBABC ABCACB AABCBC

Explanation:

The function findAllInterleavings recursively generates all possible interleavings of two strings X and Y. It builds each interleaving by choosing the next character from either X or Y while maintaining their original order. Once both strings are fully used, the resulting interleaving is added to a set to ensure uniqueness. For example, with X = "ABC" and Y = "ACB", the function outputs various interleavings like "ACBABC", "ABCACB", "AABCBC", and others, covering all possible combinations while preserving the order of characters in X and Y.