Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

Lexicographically smallest String by eradicating precisely Okay characters

[ad_1]

Given a string S consisting of solely lowercase characters, the duty is to seek out the lexicographically smallest string after eradicating precisely Okay characters from the string. However you need to 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 possibly can take away any Okay character.

NOTE: If it isn’t doable 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 ability 2, therefore okay = 2. Therefore, lexicographically smallest string after removing of two characters is “cd”.

Naive Method: The essential approach to remedy the issue is as follows:

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

Comply with the steps to resolve this downside:

  • First, appropriate 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 rely of BitSet in size.
    • If the Depend of BitSet is 1 meaning 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 larger 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 + 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 – meaning it’s faraway from the string, right here we have now to rely the variety of eliminated characters as effectively if it is the same as Okay then cease.
    • Set i = (smallest character index) + 1
  • When come out of the loop verify rely of the eliminated character is lower than Okay 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 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 resolve the issue observe the beneath thought: 

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

Comply with the steps to resolve this downside:

  • First appropriate 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) provides 0 meaning 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 larger 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 factor of the stack is larger than the char meaning we have now to contemplate the string from right here as a result of we discovered right here lowest character so we have now to take away the char from the stack and reduce Okay by one until the stack is empty or the stack prime factor is lower than the char and Okay is larger than zero (as a result of we have now to take away solely Okay characters).
    • Push the char into the stack
  • Verify 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.

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

{

    string S = "fooland";

    int Okay = 2;

  

    

    cout << lexicographicallySmallest(S, Okay);

  

    return 0;

}

Time Complexity: O(N + Okay), for traversal of each factor of the string and contained in the loop we traverse at most Okay occasions for the removing 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