Untitled

 avatar
unknown
c_cpp
5 months ago
668 B
4
Indexable
string lexicographicallySmallestString(string s, int k) {
    int n = s.size();
    unordered_map<char, int> freq;
    for (char c : s) {
        freq[c]++;
    }
    vector<char> rightMin(n, CHAR_MAX);
    for (int i = n - 2; i >= 0; --i) {
        rightMin[i] = min(s[i + 1], rightMin[i + 1]);
    }
    vector<bool> removed(n, false);
    for (int i = 0; i < n && k > 0; ++i) {
        if (freq[s[i]] > 1 && s[i] > rightMin[i]) {
            freq[s[i]]--;
            removed[i] = true;
            k--;
        }
    }
    string result;
    for (int i = 0; i < n; ++i) {
        if (!removed[i]) {
            result += s[i];
        }
    }

    return result;
}
Editor is loading...
Leave a Comment