Tuesday, December 6, 2022
HomeSoftware DevelopmentLexicographically smallest String by eradicating precisely Ok characters

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, scale back Ok by half, else multiply Ok by 2. You’ll be able to 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” 
Clarification: As the dimensions 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”
Clarification: Because the size of the string = 4,  which is 2 to the ability 2, therefore okay = 2. Therefore, lexicographically smallest string after elimination of two characters is “cd”.

Naive Strategy: The essential strategy to remedy the issue is as follows:

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

Observe the steps to resolve this drawback:

  • First, appropriate the worth of Ok by checking the size of the string is within the energy of two or not.
    • To verify the size of the string is current within the energy of two or not we will use the rely of BitSet in size.
    • If the Rely of BitSet is 1 which means string_length has just one bit which suggests it’s within the energy of two.
    • If the dimensions of the string is within the energy of two then divide Ok by 2 else multiply Ok by 2.
  • Now verify if Ok is bigger than or equal to the dimensions of the string then return -1. 
  • Else, Initialize an array of measurement string_length with 1 for marking all eliminated(0) and brought(1) components.
  • 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 rely 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 verify rely of the eliminated character is lower than Ok then take away that variety of characters from the top of the string and mark that index with zero.
  • Now run a loop from 0 to string_length and verify if the mark of that index is 1 then add the character[i] into the Ans.
  • Return the Ans.

Under is the implementation of the above strategy.

C++

  

#embody <bits/stdc++.h>

utilizing namespace std;

  

int countSetBits(int n)

{

    int rely = 0;

    whereas (n) {

        rely += n & 1;

        n >>= 1;

    }

    return rely;

}

  

string lexicographicallySmallest(string str, int okay)

{

    int n = str.measurement();

  

    

    

    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 most important()

{

    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 House: O(N), utilizing one array for marking all eliminated characters.

Optimized Strategy: To resolve the issue observe the under concept: 

The thought is to make use of stack and preserve no less than (n – Ok) non – reducing characters beginning with the smallest character we discovered.

Observe the steps to resolve this drawback:

  • First appropriate the worth of Ok by checking the size of the string is within the energy of 2 or not.
    • To verify the size of the string is current within the energy of 2 or not we will 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 suggests it’s within the energy of two.
    • If the dimensions of the string is within the energy of two then divide Ok by 2 else multiply Ok by 2.
  • Now verify if Ok is bigger than or equal to the dimensions of the string then return -1. 
  • Else, create a stack for storing the characters in non-decreasing order.
  • Run a loop and verify for each character:
    • If the highest component 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 high component 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
  • Test 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.

Under 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.high() > S[i]) {

            st.pop();

            k--;

        }

        st.push(S[i]);

    }

  

    if (okay > 0)

        whereas (k--)

            st.pop();

  

    whereas (!st.empty()) {

        ans = st.high() + ans;

        st.pop();

    }

    return ans;

}

  

int most important()

{

    string S = "fooland";

    int Ok = 2;

  

    

    cout << lexicographicallySmallest(S, Ok);

  

    return 0;

}

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

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments