Given two sorted strings S1 and S2 of lengths N and M respectively, the task is to construct lexicographically the smallest string possible by merging the two given strings and not changing the order of occurrence of characters.
Examples:
Input: S1 = “eefgkors”, S2 = “eegks”
Output: “eeeefggkkorss”
Explanation:
String “eeeefggkkorss” is lexicographically the smallest string that can be formed after merging the two given string S1 and S2.Input: S1 = “aabcdtx”, S2 = “achilp”
Output: “aaabccdhilptx”
Naive Approach: The simplest approach is to concatenate the given two strings and sort the resultant string to get lexicographically the smallest string.
Time Complexity: O(N + M)*log(N + M))
Auxiliary Space: O(N + M)
Efficient Approach: The above approach can be optimized by using the Two-Pointer technique by comparing characters of the given strings and then, construct the required string accordingly.
Follow the steps below to solve the problem:
- Initialize two pointers, say ptr1 and ptr2, pointing towards the beginning of both the strings S1 and S2 respectively.
- Initialize a string ans = “”, to store the resultant lexicographically the smallest string.
- Iterate until ptr1 is less than N and ptr2 is less than M and perform the following steps:
- If S1[ptr1] is less than the S2[ptr2], then append the character S1[ptr1] to the string ans. Increment ptr1.
- Otherwise, append the character S2[ptr2] to the string ans. Increment ptr2.
- After completing the above steps, one of the pointers doesn’t reach the end of the string.
- Therefore, add all the remaining characters of the string to the end of the string ans.
- Print ans as the resultant string.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find lexicographically// smallest string possible by merging// two sorted stringsvoid mergeStrings(string s1, string s2){ // Stores length of string s1 int len1 = s1.size(); // Stores length of string s2 int len2 = s2.size(); // Pointer to beginning // of string1 i.e., s1 int pntr1 = 0; // Pointer to beginning // of string2 i.e., s2 int pntr2 = 0; // Stores the final string string ans = ""; // Traverse the strings while (pntr1 < len1 && pntr2 < len2) { // Append the smaller of the // two current characters if (s1[pntr1] < s2[pntr2]) { ans += s1[pntr1]; pntr1++; } else { ans += s2[pntr2]; pntr2++; } } // Append the remaining characters // of any of the two strings if (pntr1 < len1) { ans += s1.substr(pntr1, len1); } if (pntr2 < len2) { ans += s2.substr(pntr2, len2); } // Print the final string cout << ans;}// Driver Codeint main(){ string S1 = "abdcdtx"; string S2 = "achilp"; // Function Call mergeStrings(S1, S2); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{ // Function to find lexicographically// smallest string possible by merging// two sorted stringsstatic void mergeStrings(String s1, String s2){ // Stores length of string s1 int len1 = s1.length(); // Stores length of string s2 int len2 = s2.length(); // Pointer to beginning // of string1 i.e., s1 int pntr1 = 0; // Pointer to beginning // of string2 i.e., s2 int pntr2 = 0; // Stores the final string String ans = ""; // Traverse the strings while (pntr1 < len1 && pntr2 < len2) { // Append the smaller of the // two current characters if (s1.charAt(pntr1) < s2.charAt(pntr2)) { ans += s1.charAt(pntr1); pntr1++; } else { ans += s2.charAt(pntr2); pntr2++; } } // Append the remaining characters // of any of the two strings if (pntr1 < len1) { ans += s1.substring(pntr1, len1); } if (pntr2 < len2) { ans += s2.substring(pntr2, len2); } // Print the final string System.out.println(ans);}// Driver Codepublic static void main (String[] args) { String S1 = "abdcdtx"; String S2 = "achilp"; // Function Call mergeStrings(S1, S2);}}// This code is contributed by sanjoy_62 |
Python3
# Python3 program for the above approach# Function to find lexicographically# smallest possible by merging# two sorted stringsdef mergeStrings(s1, s2): # Stores length of s1 len1 = len(s1) # Stores length of s2 len2 = len(s2) # Pointer to beginning # of string1 i.e., s1 pntr1 = 0 # Pointer to beginning # of string2 i.e., s2 pntr2 = 0 # Stores the final string ans = "" # Traverse the strings while (pntr1 < len1 and pntr2 < len2): # Append the smaller of the # two current characters if (s1[pntr1] < s2[pntr2]): ans += s1[pntr1] pntr1 += 1 else: ans += s2[pntr2] pntr2 += 1 # Append the remaining characters # of any of the two strings if (pntr1 < len1): ans += s1[pntr1:pntr1 + len1] if (pntr2 < len2): ans += s2[pntr2:pntr2 + len2] # Print the final string print (ans)# Driver Codeif __name__ == '__main__': S1 = "abdcdtx" S2 = "achilp" # Function Call mergeStrings(S1, S2)# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;class GFG { // Function to find lexicographically // smallest string possible by merging // two sorted strings static void mergeStrings(string s1, string s2) { // Stores length of string s1 int len1 = s1.Length; // Stores length of string s2 int len2 = s2.Length; // Pointer to beginning // of string1 i.e., s1 int pntr1 = 0; // Pointer to beginning // of string2 i.e., s2 int pntr2 = 0; // Stores the final string string ans = ""; // Traverse the strings while (pntr1 < len1 && pntr2 < len2) { // Append the smaller of the // two current characters if (s1[pntr1] < s2[pntr2]) { ans += s1[pntr1]; pntr1++; } else { ans += s2[pntr2]; pntr2++; } } // Append the remaining characters // of any of the two strings if (pntr1 < len1) { ans += s1.Substring(pntr1, len1 - pntr1); } if (pntr2 < len2) { ans += s2.Substring(pntr2, len2 - pntr2); } // Print the final string Console.WriteLine(ans); } // Driver Code public static void Main() { string S1 = "abdcdtx"; string S2 = "achilp"; // Function Call mergeStrings(S1, S2); }}// This code is contributed by ukasp. |
Javascript
<script> // Javascript program for the above approach// Function to find lexicographically// smallest string possible by merging// two sorted stringsfunction mergeStrings( s1, s2){ // Stores length of string s1 var len1 = s1.length; // Stores length of string s2 var len2 = s2.length; // Pointer to beginning // of string1 i.e., s1 var pntr1 = 0; // Pointer to beginning // of string2 i.e., s2 var pntr2 = 0; // Stores the final string var ans = ""; // Traverse the strings while (pntr1 < len1 && pntr2 < len2) { // Append the smaller of the // two current characters if (s1[pntr1] < s2[pntr2]) { ans += s1[pntr1]; pntr1++; } else { ans += s2[pntr2]; pntr2++; } } // Append the remaining characters // of any of the two strings if (pntr1 < len1) { ans += s1.substr(pntr1, len1); } if (pntr2 < len2) { ans += s2.substr(pntr2, len2); } // Print the final string document.write( ans);}// Driver Codevar S1 = "abdcdtx";var S2 = "achilp";// Function CallmergeStrings(S1, S2);</script> |
Output:
aabcdcdhilptx
Time Complexity: O(N + M)
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!
