Lexicographic smallest permutation of a String containing the second String as a Substring

0 0 6 minutes read

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 = “zambiatek”, 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 string
string 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 Code
int main()
{
    string str1 = "zambiatekfor";
    string str2 = "for";
    cout << findSmallestString(str1, str2);
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
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];
    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 Code
public static void main(String[] args)
{
    String str1 = "zambiatekfor";
    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 code
str1 = "zambiatekfor"
str2 = "for"
 
print(findSmallestString(str1, str2))
 
# This code is contributed by Stuti Pathak

C#

// C# program to implement
// the above approach
using 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 = "zambiatekfor";
        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 = "zambiatekfor";
    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 zambiatek!