Given two strings str1 and str2, the task is to find the lexicographic smallest permutation of str1 that contains str2 as a substring.
Note: Assume that the solution always exists.
Example:
Input: str1 = “abab”, str2 = “ab”
Output: “aabb”
Explanation: The Lexicographically smallest permutation of string str1 is “aabb”, Since “aabb” contains the string “ab” as a substring, therefore, “aabb” is the required answer.Input: str1 = “neveropen”, str2 = “for”
Output: “eeeeforggkkss”
Approach: This problem can be solved using the concept of the Frequency Counting technique. Follow the steps below to solve this problem.
- Store the frequency of all the characters of the strings str1 and str2.
- Initialize the resultant string with the substring.
- Subtract the frequency of the second string from the frequency of the first string
- Now, append the remaining characters which are lexicographically smaller than or equal to the first character of the substring before the substring in the resultant string.
- Append the remaining characters in the lexicographical order behind the substring in the resultant string.
- Finally, print the resultant string.
Below is the implementation of the above approach.
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to print the desired// lexicographic smaller stringstring findSmallestString(string str1, string str2){ int freq1[26], freq2[26]; memset(freq1, 0, sizeof freq1); memset(freq2, 0, sizeof freq2); // Calculate length of the string int n1 = str1.length(); int n2 = str2.length(); // Stores the frequencies of // characters of string str1 for (int i = 0; i < n1; ++i) { freq1[str1[i] - 'a']++; } // Stores the frequencies of // characters of string str2 for (int i = 0; i < n2; ++i) { freq2[str2[i] - 'a']++; } // Decrease the frequency of // second string from that of // of the first string for (int i = 0; i < 26; ++i) { freq1[i] -= freq2[i]; } // To store the resultant string string res = ""; // To find the index of first // character of the string str2 int minIndex = str2[0] - 'a'; // Append the characters in // lexicographical order for (int i = 0; i < 26; ++i) { // Append all the current // character (i + 'a') for (int j = 0; j < freq1[i]; ++j) { res += (char)(i + 'a'); } // If we reach first character // of string str2 append str2 if (i == minIndex) { res += str2; } } // Return the resultant string return res;}// Driver Codeint main(){ string str1 = "neveropenfor"; string str2 = "for"; cout << findSmallestString(str1, str2);} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{// Function to print the desired// lexicographic smaller Stringstatic String findSmallestString(String str1, String str2){ int []freq1 = new int[26]; int []freq2 = new int[26]; Arrays.fill(freq1, 0); Arrays.fill(freq2, 0); // Calculate length of the String int n1 = str1.length(); int n2 = str2.length(); // Stores the frequencies of // characters of String str1 for(int i = 0; i < n1; ++i) { freq1[str1.charAt(i) - 'a']++; } // Stores the frequencies of // characters of String str2 for(int i = 0; i < n2; ++i) { freq2[str2.charAt(i) - 'a']++; } // Decrease the frequency of // second String from that of // of the first String for(int i = 0; i < 26; ++i) { freq1[i] -= freq2[i]; } // To store the resultant String String res = ""; // To find the index of first // character of the String str2 int minIndex = str2.charAt(0) - 'a'; // Append the characters in // lexicographical order for(int i = 0; i < 26; ++i) { // Append all the current // character (i + 'a') for(int j = 0; j < freq1[i]; ++j) { res += (char)(i + 'a'); } // If we reach first character // of String str2 append str2 if (i == minIndex) { res += str2; } } // Return the resultant String return res;}// Driver Codepublic static void main(String[] args){ String str1 = "neveropenfor"; String str2 = "for"; System.out.print(findSmallestString(str1, str2));}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program to implement # the above approach # Function to print the desired # lexicographic smaller string def findSmallestString(str1, str2): freq1 = [0] * 26 freq2 = [0] * 26 # Calculate length of the string n1 = len(str1) n2 = len(str2) # Stores the frequencies of # characters of string str1 for i in range(n1): freq1[ord(str1[i]) - ord('a')] += 1 # Stores the frequencies of # characters of string str2 for i in range(n2): freq2[ord(str2[i]) - ord('a')] += 1 # Decrease the frequency of # second string from that of # of the first string for i in range(26): freq1[i] -= freq2[i] # To store the resultant string res = "" # To find the index of first # character of the string str2 minIndex = ord(str2[0]) - ord('a') # Append the characters in # lexicographical order for i in range(26): # Append all the current # character (i + 'a') for j in range(freq1[i]): res += chr(i+ ord('a')) # If we reach first character # of string str2 append str2 if i == minIndex: res += str2 # Return the resultant string return res# Driver codestr1 = "neveropenfor"str2 = "for"print(findSmallestString(str1, str2))# This code is contributed by Stuti Pathak |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function to print the desired // lexicographic smaller String static String findSmallestString(String str1, String str2) { int[] freq1 = new int[26]; int[] freq2 = new int[26]; // Calculate length of the String int n1 = str1.Length; int n2 = str2.Length; // Stores the frequencies of // characters of String str1 for (int i = 0; i < n1; ++i) { freq1[str1[i] - 'a']++; } // Stores the frequencies of // characters of String str2 for (int i = 0; i < n2; ++i) { freq2[str2[i] - 'a']++; } // Decrease the frequency of // second String from that of // of the first String for (int i = 0; i < 26; ++i) { freq1[i] -= freq2[i]; } // To store the resultant String String res = ""; // To find the index of first // character of the String str2 int minIndex = str2[0] - 'a'; // Append the characters in // lexicographical order for (int i = 0; i < 26; ++i) { // Append all the current // character (i + 'a') for (int j = 0; j < freq1[i]; ++j) { res += (char)(i + 'a'); } // If we reach first character // of String str2 append str2 if (i == minIndex) { res += str2; } } // Return the resultant String return res; } // Driver Code public static void Main(String[] args) { String str1 = "neveropenfor"; String str2 = "for"; Console.Write(findSmallestString(str1, str2)); }}// This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript program to implement // the above approach // Function to print the desired // lexicographic smaller String function findSmallestString(str1, str2) { let freq1 = Array.from({length: 26}, (_, i) => 0); let freq2 = Array.from({length: 26}, (_, i) => 0); // Calculate length of the String let n1 = str1.length; let n2 = str2.length; // Stores the frequencies of // characters of String str1 for (let i = 0; i < n1; ++i) { freq1[str1[i].charCodeAt() - 'a'.charCodeAt()]++; } // Stores the frequencies of // characters of String str2 for (let i = 0; i < n2; ++i) { freq2[str2[i].charCodeAt() - 'a'.charCodeAt()]++; } // Decrease the frequency of // second String from that of // of the first String for (let i = 0; i < 26; ++i) { freq1[i] -= freq2[i]; } // To store the resultant String let res = ""; // To find the index of first // character of the String str2 let minIndex = str2[0].charCodeAt() - 'a'.charCodeAt(); // Append the characters in // lexicographical order for (let i = 0; i < 26; ++i) { // Append all the current // character (i + 'a') for (let j = 0; j < freq1[i]; ++j) { res += String.fromCharCode(i + 'a'.charCodeAt()); } // If we reach first character // of String str2 append str2 if (i == minIndex) { res += str2; } } // Return the resultant String return res; } // Driver code let str1 = "neveropenfor"; let str2 = "for"; document.write(findSmallestString(str1, str2));</script> |
Output:
eeeefforggkkorss
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
