Lexicographically smallest String by eradicating precisely Okay characters

[ad_1]

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

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

Examples:

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

Enter: S = “code”, Okay = 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 elimination of two characters is “cd”.

Naive Method: The fundamental method to remedy the issue is as follows:

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

Observe the steps to resolve this downside:

  • First, right the worth of Okay 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 are able to use the depend of BitSet in size.
    • If the Depend of BitSet is 1 which means string_length has just one bit which implies it’s within the energy of two.
    • If the dimensions of the string is within the energy of two then divide Okay by 2 else multiply Okay by 2.
  • Now verify if Okay is bigger than or equal to the dimensions of the string then return -1. 
  • Else, Initialize an array of dimension 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 + Okay 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’ve got to depend the variety of eliminated characters as nicely if it is the same as Okay then cease.
    • Set i = (smallest character index) + 1
  • When come out of the loop verify depend of the eliminated character is lower than Okay 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 verify 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 method.

C++

  

#embrace <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 primary()

{

    string S = "fooland";

    int Okay = 2;

  

    

    cout << lexicographicallySmallest(S, Okay) << 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 Method: To unravel the issue comply with the under thought: 

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

Observe the steps to resolve this downside:

  • First right the worth of Okay 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 are able to use the Bitwise-and operator. 
    • If Bitwise-and of string_length and (string_length – 1) offers 0 which means string_length has just one bit which implies it’s within the energy of two.
    • If the dimensions of the string is within the energy of two then divide Okay by 2 else multiply Okay by 2.
  • Now verify if Okay 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’ve got to think about the string from right here as a result of we discovered right here lowest character so we’ve got to take away the char from the stack and reduce Okay by one until the stack is empty or the stack prime component is lower than the char and Okay is bigger than zero (as a result of we’ve got to take away solely Okay characters).
    • Push the char into the stack
  • Test if the variety of eliminated chars is lower than Okay 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 method.

C++

  

#embrace <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 primary()

{

    string S = "fooland";

    int Okay = 2;

  

    

    cout << lexicographicallySmallest(S, Okay);

  

    return 0;

}

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

[ad_2]

Leave a Reply