#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// An interleaved string two strings preserves the order of characters in individual strings
void print_interleaving_strings(char* str1, char* str2, char* interleaved, size_t len1, size_t len2, int i) {
if (len1 == 0 && len2 == 0) {
printf("%s\n", interleaved);
}
if (len1 != 0) {
interleaved[i] = str1[0];
print_interleaving_strings(str1 + 1, str2, interleaved, len1 - 1, len2, i + 1);
}
if (len2 != 0) {
interleaved[i] = str2[0];
print_interleaving_strings(str1, str2 + 1, interleaved, len1, len2 - 1, i + 1);
}
}
void interleaving_strings(char* str1, char* str2, size_t len1, size_t len2) {
char* interleaved = malloc(sizeof(char) * (len1 + len2 + 1));
interleaved[len1 + len2] = '\0';
print_interleaving_strings(str1, str2, interleaved, len1, len2, 0);
free(interleaved);
}
int main() {
char str1[] = "AB";
char str2[] = "CD";
interleaving_strings(str1, str2, strlen(str1), strlen(str2));
return 0;
}
// preserves the order = 'A' comes before 'B' and 'C' comes before 'D'
/*
run:
ABCD
ACBD
ACDB
CABD
CADB
CDAB
*/
