Generate longest String with character sum at most Okay by deleting letters

Given a string str and an integer Okay, the duty is to seek out the longest string that may be made by deleting letters from the given string such that the sum of the characters of the remaining string is at most Okay.

Observe: The worth of the string is calculated because the sum of the worth of characters (a worth is 1, b worth is 2…., z worth is 26).

Examples:

Enter:  str = “geeksforgeeks”, Okay = 15
Output: eee
Clarification: After deleting the characters string will get lowered to eee whose worth is 5 + 5 +  5 = 15 which is lower than or equal to Okay i.e. 15

Enter: str = “abca”, Okay = 6
Output: aba
Clarification: Preliminary worth of str 1 + 2 + 3 + 1 = 7, after deleting the letter c, the string will get lowered to aba whose worth is 1+2+1 = 4 which is lower than Okay i.e. 6.

Strategy: The issue will be solved utilizing Grasping strategy based mostly on the next thought:

We should delete letters with the best worth first. So, we kind the string str in reducing order and shall be deleting letters from the beginning of string str so long as the preliminary worth of string str is larger than the given worth Okay.

Comply with the steps talked about under to implement the concept:

• Calculate the preliminary worth of the given string.
• Type the string str in reducing order
• Begin eradicating the worth of the present letter from the preliminary worth so long as the preliminary worth is larger than Okay.
  • Retailer the eliminated characters within the map
• Iterate by the given string as soon as once more and 
  • If the present letter doesn’t exist within the map take it into the resultant string
  • Else lower the frequency of the letter
• Return the resultant string

Beneath is the implementation of the above strategy:

// C++ code to implement the strategy

#embody <bits/stdc++.h>
utilizing namespace std;

// Perform for locating out string with worth
// lower than or equal to Okay
string minimise_str(string str, int Okay)
{
    int initial_value = 0;

    // Calculate preliminary worth of string
    for (int i = 0; i < str.size(); i++) {
        initial_value += (str[i] - 'a') + 1;
    }

    string temp = str;

    // Type the string in reducing order
    kind(str.start(), str.finish());
    reverse(str.start(), str.finish());

    // Retailer the deleted letters
    unordered_map<char, int> mpp;
    int i = 0;

    // Take away letters so long as the preliminary
    // worth is larger than Okay
    whereas (initial_value > Okay) {
        initial_value -= (str[i] - 'a') + 1;
        mpp[str[i]]++;
        i++;
    }

    // Retailer resultant string
    string ans = "";
    for (int i = 0; i < temp.dimension(); i++) {

        // If letter do exist in map, lower
        // frequency
        if (mpp[temp[i]] > 0) {
            mpp[temp[i]]--;
        }
        // Else retailer the letter in resultant
        // string
        else {
            ans += temp[i];
        }
    }

    // Return resultant string
    return ans;
}

// Driver code
int predominant()
{
    string str = "geeksforgeeks";
    int Okay = 15;

    // Perform name
    cout << minimise_str(str, Okay);

    return 0;
}

Time Complexity: O(N * logN)
Auxiliary House: O(N)

Associated Articles: