Thursday, July 14, 2022
HomeWordPress DevelopmentConstruct lexicographically smallest String from two given Strings

Construct lexicographically smallest String from two given Strings


View Dialogue

Enhance Article

Save Article

Like Article

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.
  • Return the resultant string.

Beneath is the implementation of the above strategy.

C++

  

#embody <bits/stdc++.h>

utilizing namespace std;

  

#outline ll lengthy lengthy

  

string buildString(string a, string b, int ok)

{

    

    ll n = a.measurement();

    ll m = b.measurement();

  

    

    type(a.start(), a.finish());

    type(b.start(), b.finish());

  

    

    ll i = 0, j = 0, p = 0, q = 0;

  

    string c = "";

  

    

    whereas (i < n && j < m) {

        if ((a[i] < b[j] && p < ok) || q == ok) {

            c += a[i];

            p++;

            i++;

            q = 0;

        }

        else {

            c += b[j];

            q++;

            j++;

            p = 0;

        }

    }

  

    

    return c;

}

  

int foremost()

{

  

    string X = "aaaa";

    string Y = "bbbb";

    int Okay = 2;

  

    

    cout << buildString(X, Y, Okay) << endl;

  

    return 0;

}

Time Complexity: O(N*logN +M*logM)
Auxiliary Area: O(N+M)

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -
Google search engine

Most Popular

Recent Comments