Given two strings X and Y of lowercase letters, of length N and M respectively, the task is to build another string Z by performing two types of operations:
- Choose any character from the string X, remove it from X, and add it to the end of Z.
- Choose any character from the string Y, remove it from Y, and add it to the end of Z.
Note: You can only K consecutive operations in a single string. Perform the operations until either X or Y becomes empty.
Examples:
Input: X = “aaaa”, Y =”bbbb”, K = 2
Output: aabaa
Explanation: The smallest lexicographically string possible for K = 2 is “aabaa”.
Select “aa” from X. Then select “b” from Y and “aa” from X again.Input: X = “ccaaa”, Y =”bbeedd”, K = 3
Output: aaabbcc
Approach: To solve the problem follow the below idea:
We solve this problem by using greedy method.
Sort the strings X and Y and take the characters as follows:
- Keep selecting consecutive characters from the string whose characters are lexicographically smaller till K consecutive characters are selected, or all the characters of that string are selected or the character of the other string becomes lexicographically smaller.
- If K consecutive characters are selected, then do the above operation again on the other string. Repeat these two processes till at least one of the string becomes empty.
Follow the below steps to solve the problem:
- Sort the strings in ascending order.
- Initialize the pointers i, j, p, q to 0.
- Run the loop while any of the strings is non-empty.
- If (X[i] < Y[j] and p < k) or q == k, then,
- Append X[i] to the end of Z and increment i and p by 1 and set q = 0.
- Otherwise, do the following:
- Append Y[j] to the end of Z and increment j and q by 1 and also set p to 0.
- If (X[i] < Y[j] and p < k) or q == k, then,
- Return the resultant string.
Below is the implementation of the above approach.
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;#define ll long long// Function to build smallest lexicographically// string possible for given Kstring buildString(string a, string b, int k){ // Calculate the sizes ll n = a.size(); ll m = b.size(); // Sort the strings sort(a.begin(), a.end()); sort(b.begin(), b.end()); // Initialize the pointers ll i = 0, j = 0, p = 0, q = 0; string c = ""; // While any of string is non-empty while (i < n && j < m) { if ((a[i] < b[j] && p < k) || q == k) { c += a[i]; p++; i++; q = 0; } else { c += b[j]; q++; j++; p = 0; } } // Return resultant string return c;}// Driver Codeint main(){ string X = "aaaa"; string Y = "bbbb"; int K = 2; // Function call cout << buildString(X, Y, K) << endl; return 0;} |
Java
// JAVA code to implement the above approachimport java.util.Arrays;import java.util.Scanner;import java.io.*;class GFG{ // Function to build smallest lexicographically // string possible for given k static String buildstring(String a, String b, int k) { // Calculate the sizes int n = a.length(); int m = b.length(); //Sort the strings char c1[] = a.toCharArray(); Arrays.sort(c1); a = new String(c1); char c2[] = b.toCharArray(); Arrays.sort(c2); b = new String(c2); // Initialize the pointers int i = 0, j = 0, p = 0, q = 0; String c = ""; // While any of string is non-empty while (i < n && j < m) { if ((a.charAt(i) < b.charAt(j) && p < k) || q == k) { c += a.charAt(i); p++; i++; q = 0; } else { c += b.charAt(j); q++; j++; p = 0; } } // Return resultant string return c; } // driver code public static void main (String[] args) { String x = "aaaa"; String y = "bbbb"; int k = 2; // function call System.out.println(buildstring(x,y,k)); }}// This code is written by Ujjwal Kumar Bhardwaj |
Python3
# Python3 code to implement the above approach# Function to build smallest lexicographically# string possible for given Kdef buildString(a, b, k) : # Calculate the sizes n = len(a); m = len(b); a = list(a) b = list(b) # Sort the strings a.sort(); b.sort(); # Initialize the pointers i = 0; j = 0; p = 0; q = 0; c = ""; # While any of string is non-empty while (i < n and j < m) : if ((a[i] < b[j] and p < k) or q == k) : c += a[i]; p += 1; i += 1; q = 0; else : c += b[j]; q += 1; j += 1; p = 0; c = "".join(c) # Return resultant string return c;# Driver Codeif __name__ == "__main__" : X = "aaaa"; Y = "bbbb"; K = 2; # Function call print(buildString(X, Y, K)); # This code is contributed by AnkThon |
C#
// C# code to implement the above approachusing System;using System.Collections;public class GFG { // Function to build smallest lexicographically // string possible for given k static String buildstring(String a, String b, int k) { // Calculate the sizes int n = a.Length; int m = b.Length; // Sort the strings char[] c1 = a.ToCharArray(); Array.Sort(c1); a = new String(c1); char[] c2 = b.ToCharArray(); Array.Sort(c2); b = new String(c2); // Initialize the pointers int i = 0, j = 0, p = 0, q = 0; String c = ""; // While any of string is non-empty while (i < n && j < m) { if ((a[i] < b[j] && p < k) || q == k) { c += a[i]; p++; i++; q = 0; } else { c += b[j]; q++; j++; p = 0; } } // Return resultant string return c; } static public void Main() { // Code String x = "aaaa"; String y = "bbbb"; int k = 2; // function call Console.WriteLine(buildstring(x, y, k)); }}// This code is written by lokeshmvs21. |
Javascript
<script>// Javascript code to implement the above approach// Function to build smallest lexicographically// string possible for given Kfunction buildString( a, b, k){ // Calculate the sizes let n = a.length; let m = b.length; // Sort the strings a.sort; b.sort; // Initialize the pointers let i = 0, j = 0, p = 0, q = 0; let c = ""; // While any of string is non-empty while (i < n && j < m) { if ((a[i] < b[j] && p < k) || q == k) { c += a[i]; p++; i++; q = 0; } else { c += b[j]; q++; j++; p = 0; } } // Return resultant string return c;}// Driver Code let X = "aaaa"; let Y = "bbbb"; let K = 2; // Function call document.write(buildString(X, Y, K));// This code is contributed by hrithikgarg03188.</script> |
Output
aabaa
Time Complexity: O(N*logN +M*logM)
Auxiliary Space: O(N+M)
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!
