Given two strings str1 and str2 of lengths M and N respectively. The task is to find all the distinct strings of length M + N such that the frequency of any character in the resultant string is equal to the sum of frequencies of the same character in the given strings and both the given strings are present as a sub-sequence in all the generated strings.
Examples:
Input: str = “aa”, str2 = “ab”
Output:
abaa
aaab
aaba
Input: str1 = “ab”, str2 = “de”
Output:
deab
daeb
adeb
abde
dabe
adbe
Approach: This problem can be solved using recursion. Set two pointers i and j to the beginnings of strings str1 and str2 respectively. Now, at every recursive call, we have two choices to select either the character at str1[i] or the character at str2[j] and the termination condition will be when the length of the resultant string becomes equal to len(str1) + len(str2). Use an unordered_set in order to avoid duplicates.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Set to store strings// and avoid duplicatesset<string> stringSet;// Recursive function to generate the required stringsvoid find_permutation(string& str1, string& str2, int len1, int len2, int i, int j, string res){ // If current string is part of the result if (res.length() == len1 + len2) { // Insert it into the set stringSet.insert(res); return; } // If character from str1 can be chosen if (i < len1) find_permutation(str1, str2, len1, len2, i + 1, j, res + str1[i]); // If character from str2 can be chosen if (j < len2) find_permutation(str1, str2, len1, len2, i, j + 1, res + str2[j]);}// Function to print the generated// strings from the setvoid print_set(){ set<string>::iterator itr; for (itr = stringSet.begin(); itr != stringSet.end(); itr++) cout << (*itr) << endl;}// Driver codeint main(){ string str1 = "aa", str2 = "ab"; int len1 = str1.length(); int len2 = str2.length(); find_permutation(str1, str2, len1, len2, 0, 0, ""); print_set(); return 0;} |
Java
// Java implementation of the approachimport java.util.HashSet;class GFG{ // Set to store strings // and avoid duplicates static HashSet<String> stringSet = new HashSet<>(); // Recursive function to generate the required strings public static void find_permutation(String str1, String str2, int len1, int len2, int i, int j, String res) { // If current string is part of the result if (res.length() == len1 + len2) { // Insert it into the set stringSet.add(res); return; } // If character from str1 can be chosen if (i < len1) find_permutation(str1, str2, len1, len2, i + 1, j, res + str1.charAt(i)); // If character from str2 can be chosen if (j < len2) find_permutation(str1, str2, len1, len2, i, j + 1, res + str2.charAt(j)); } // Function to print the generated // strings from the set public static void print_set() { for (String s : stringSet) System.out.println(s); } // Driver code public static void main(String[] args) { String str1 = "aa", str2 = "ab"; int len1 = str1.length(); int len2 = str2.length(); find_permutation(str1, str2, len1, len2, 0, 0, ""); print_set(); }}// This code is contributed by// sanjeev2552 |
Python3
# Python3 implementation of the approach# Set to store strings# and avoid duplicatesstringSet=dict()# Recursive function to generate the required stringsdef find_permutation( str1,str2,len1,len2,i,j,res): # If current string is part of the result if (len(res) == len1 + len2): # Insert it into the set stringSet[res]=1 return # If character from str1 can be chosen if (i < len1): find_permutation(str1, str2, len1, len2,i + 1, j, res + str1[i]) # If character from str2 can be chosen if (j < len2): find_permutation(str1, str2, len1, len2,i, j + 1, res + str2[j])# Function to print the generated# strings from the setdef print_set(): for i in stringSet: print(i)# Driver codestr1 = "aa"str2 = "ab"len1 = len(str1)len2 = len(str2)find_permutation(str1, str2, len1,len2, 0, 0, "")print_set()# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approachusing System;using System.Collections.Generic; class GFG{ // Set to store strings // and avoid duplicates static HashSet<String> stringSet = new HashSet<String>(); // Recursive function to generate the required strings public static void find_permutation(String str1, String str2, int len1, int len2, int i, int j, String res) { // If current string is part of the result if (res.Length == len1 + len2) { // Insert it into the set stringSet.Add(res); return; } // If character from str1 can be chosen if (i < len1) find_permutation(str1, str2, len1, len2, i + 1, j, res + str1[i]); // If character from str2 can be chosen if (j < len2) find_permutation(str1, str2, len1, len2, i, j + 1, res + str2[j]); } // Function to print the generated // strings from the set public static void print_set() { foreach (String s in stringSet) Console.WriteLine(s); } // Driver code public static void Main(String[] args) { String str1 = "aa", str2 = "ab"; int len1 = str1.Length; int len2 = str2.Length; find_permutation(str1, str2, len1, len2, 0, 0, ""); print_set(); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approach// Set to store strings // and avoid duplicateslet stringSet = new Set();// Recursive function to generate the required stringsfunction find_permutation(str1,str2,len1,len2,i,j,res){ // If current string is part of the result if (res.length == len1 + len2) { // Insert it into the set stringSet.add(res); return; } // If character from str1 can be chosen if (i < len1) find_permutation(str1, str2, len1, len2, i + 1, j, res + str1[i]); // If character from str2 can be chosen if (j < len2) find_permutation(str1, str2, len1, len2, i, j + 1, res + str2[j]);}// Function to print the generated // strings from the setfunction print_set(){ for(let s of stringSet.values()) { document.write(s+"<br>"); }}// Driver codelet str1 = "aa", str2 = "ab";let len1 = str1.length;let len2 = str2.length;find_permutation(str1, str2, len1, len2, 0, 0, "");print_set();// This code is contributed by unknown2108</script> |
Output
aaab aaba abaa
Time complexity: O(
)
Auxiliary Space: O(length(str1)+length(str2))
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!