Software Development

Lexicographically smallest String by eradicating precisely Ok characters


Given a string S consisting of solely lowercase characters, the duty is to seek out the lexicographically smallest string after eradicating precisely Ok characters from the string. However it’s a must to modify the worth of Ok, i.e., if the size of the string is an influence of two, cut back Ok by half, else multiply Ok by 2. You may take away any Ok character.

NOTE: If it isn’t attainable to take away Ok (the worth of Ok after correction) characters or if the ensuing string is empty return -1.

Examples:

Enter: S = “fooland”, Ok = 2
Output: “and” 
Rationalization: As the scale of the string = 7, which isn’t an influence of two, therefore Ok = 4. After eradicating 4 characters from the given string, the lexicographically smallest string is “and”.

Enter: S = “code”, Ok = 4
Output: “cd”
Rationalization: Because the size of the string = 4,  which is 2 to the facility 2, therefore okay = 2. Therefore, lexicographically smallest string after removing of two characters is “cd”.

Naive Strategy: The fundamental technique to resolve the issue is as follows:

The concept is to seek out the smallest (n – Ok) characters from string utilizing nested loop.

Comply with the steps to resolve this downside:

  • First, appropriate the worth of Ok by checking the size of the string is within the energy of two or not.
    • To examine the size of the string is current within the energy of two or not we are able to use the depend of BitSet in size.
    • If the Rely of BitSet is 1 which means string_length has just one bit which implies it’s within the energy of two.
    • If the scale of the string is within the energy of two then divide Ok by 2 else multiply Ok by 2.
  • Now examine if Ok is bigger than or equal to the scale of the string then return -1. 
  • Else, Initialize an array of dimension string_length with 1 for marking all eliminated(0) and brought(1) parts.
  • Run a loop from 0 to the finish of string_length
    • Run a nested loop contained in the higher loop from the higher loop’s index until index + Ok and discover the smallest character between the vary.
    • Now run a loop from (smallest character index) – 1 until the higher loop index and marks all index with zero – which means it’s faraway from the string, right here we now have to depend the variety of eliminated characters as properly if it is the same as Ok then cease.
    • Set i = (smallest character index) + 1
  • When come out of the loop examine depend of the eliminated character is lower than Ok then take away that variety of characters from the tip of the string and mark that index with zero.
  • Now run a loop from 0 to string_length and examine if the mark of that index is 1 then add the character[i] into the Ans.
  • Return the Ans.

Beneath is the implementation of the above strategy.

C++

  

#embody <bits/stdc++.h>

utilizing namespace std;

  

int countSetBits(int n)

    int depend = 0;

    whereas (n)

        depend += n & 1;

        n >>= 1;

    

    return depend;

  

string lexicographicallySmallest(string str, int okay)

    int n = str.dimension();

  

    

    

    if (countSetBits(n) == 1)

        okay /= 2;

  

    

    else

        okay *= 2;

  

    

    

    if (okay >= n)

        return "-1";

  

    

    int a[n], i, j;

  

    

    for (i = 0; i < n; i++)

        a[i] = 1;

  

    

    for (i = 0; i < n;)

  

        

        int begin = i;

  

        

        int index = begin;

  

        

        int finish = min(begin + okay, n - 1);

  

        

        char minn = str[start];

  

        

        for (j = begin + 1; j <= finish; j++)

  

            

            

            if (str[j] < minn)

                minn = str[j];

                index = j;

            

        

  

        

        for (j = index - 1; j >= begin and okay != 0; j--)

            a[j] = 0;

            k--;

        

  

        

        i = index + 1;

    

  

    

    

    if (okay)

        for (i = n - 1; i >= 0 and okay != 0; i--)

            if (a[i])

                a[i] = 0;

                k--;

            

        

    

  

    

    string res = "";

  

    

    for (i = 0; i < n; i++)

        if (a[i])

            res += str[i];

        

    

  

    

    return res;

  

int fundamental()

    string S = "fooland";

    int Ok = 2;

  

    

    cout << lexicographicallySmallest(S, Ok) << endl;

  

    return 0;

Time Complexity: O(N*N), As right here we run a nested loop.
Auxiliary Area: O(N), utilizing one array for marking all eliminated characters.

Optimized Strategy: To unravel the issue observe the beneath concept: 

The concept is to make use of stack and preserve a minimum of (n – Ok) non – reducing characters beginning with the smallest character we discovered.

Comply with the steps to resolve this downside:

  • First appropriate the worth of Ok by checking the size of the string is within the energy of 2 or not.
    • To examine the size of the string is current within the energy of 2 or not we are able to use the Bitwise-and operator. 
    • If Bitwise-and of string_length and (string_length – 1) provides 0 which means string_length has just one bit which implies it’s within the energy of two.
    • If the scale of the string is within the energy of two then divide Ok by 2 else multiply Ok by 2.
  • Now examine if Ok is bigger than or equal to the scale of the string then return -1. 
  • Else, create a stack for storing the characters in non-decreasing order.
  • Run a loop and examine for each character:
    • If the highest ingredient of the stack is bigger than the char which means we now have to think about the string from right here as a result of we discovered right here lowest character so we now have to take away the char from the stack and reduce Ok by one until the stack is empty or the stack prime ingredient is lower than the char and Ok is bigger than zero (as a result of we now have to take away solely Ok characters).
    • Push the char into the stack
  • Examine if the variety of eliminated chars is lower than Ok then take away that variety of chars from the stack.
  • Copy all stack characters right into a variable string ans and reverse the ans(as a result of we copied from the stack).
  • Return the Ans.

Beneath is the implementation of the above strategy.

C++

  

#embody <bits/stdc++.h>

utilizing namespace std;

  

string lexicographicallySmallest(string S, int okay)

    string ans = "";

    int l = S.size();

  

    if (l & (l - 1))

        okay += okay;

    else

        okay /= 2;

  

    if (okay >= l)

        return "-1";

  

    stack<char> st;

    for (int i = 0; i < l; i++)

        whereas (!st.empty() && okay > 0 && st.prime() > S[i])

            st.pop();

            k--;

        

        st.push(S[i]);

    

  

    if (okay > 0)

        whereas (k--)

            st.pop();

  

    whereas (!st.empty())

        ans = st.prime() + ans;

        st.pop();

    

    return ans;

  

int fundamental()

    string S = "fooland";

    int Ok = 2;

  

    

    cout << lexicographicallySmallest(S, Ok);

  

    return 0;

Time Complexity: O(N + Ok), for traversal of each ingredient of the string and contained in the loop we traverse at most Ok occasions for the removing of strings from the stack so total time is O(N + Ok).
Auxiliary Area: O(N), For storing characters within the stack.

What's your reaction?

Leave A Reply

Your email address will not be published. Required fields are marked *