Given two strings X and Y of lowercase letters, of size N and M respectively, the duty is to construct one other string Z by performing two varieties of operations:
- Select any character from the string X, take away it from X, and add it to the tip of Z.
- Select any character from the string Y, take away it from Y, and add it to the tip of Z.
Word: You possibly can solely Okay consecutive operations in a single string. Carry out the operations till both X or Y turns into empty.
Examples:
Enter: X = “aaaa”, Y =”bbbb”, Okay = 2
Output: aabaa
Rationalization: The smallest lexicographically string doable for Okay = 2 is “aabaa”.
Choose “aa” from X. Then choose “b” from Y and “aa” from X once more.Enter: X = “ccaaa”, Y =”bbeedd”, Okay = 3
Output: aaabbcc
Strategy: To resolve the issue observe the beneath thought:
We resolve this downside by utilizing grasping methodology.
Kind the strings X and Y and take the characters as follows:
- Preserve deciding on consecutive characters from the string whose characters are lexicographically smaller until Okay consecutive characters are chosen, or all of the characters of that string are chosen or the character of the opposite string turns into lexicographically smaller.
- If Okay consecutive characters are chosen, then do the above operation once more on the opposite string. Repeat these two processes until no less than one of many string turns into empty.
Observe the beneath steps to unravel the issue:
- Kind the strings in ascending order.
- Initialize the pointers i, j, p, q to 0.
- Run the loop whereas any of the strings is non-empty.
- If (X[i] < Y[j] and p < ok) or q == ok, then,
- Append X[i] to the tip of Z and increment i and p by 1 and set q = 0.
- In any other case, do the next:
- Append Y[j] to the tip of Z and increment j and q by 1 and in addition set p to 0.
- If (X[i] < Y[j] and p < ok) or q == ok, then,
- Return the resultant string.
Beneath is the implementation of the above strategy.
C++
|
|
Time Complexity: O(N*logN +M*logM)
Auxiliary Area: O(N+M)
