Skip to content

Apply Operations to Make String Empty⚓︎

Link

Solution⚓︎

Way 1⚓︎

See reference (Chinese).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    string lastNonEmptyString(string s) {
        vector<int> count(26), last(26);
        for (int i = 0; i < s.size(); i++) {
            int offset = s[i] - 'a';
            count[offset]++;
            last[offset] = i;
        }

        vector<int> ids;
        int mx = *max_element(count.begin(), count.end());
        for (int i = 0; i < 26; i++) {
            if (count[i] == mx) {
                ids.push_back(last[i]);
            }
        }

        sort(ids.begin(), ids.end());

        string t(ids.size(), 0);
        for (int i = 0; i < ids.size(); i++) {
            t[i] = s[ids[i]];
        }
        return t;
    }
};
  • Time complexity: \(O\left( n+\left| \Sigma \right|\log \left| \Sigma \right| \right)\), where \(\left| \Sigma \right| = 26\);
  • Space complexity: \(O\left( \left| \Sigma \right| \right)\).

Way 2⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string lastNonEmptyString(string s) {
        unordered_map<char, int> mapping;
        int mx = 0;
        for (char ch : s) {
            mapping[ch]++;
            mx = max(mapping[ch], mx);
        }

        string res = "";
        for (int i = s.size() - 1; i >= 0; i--) {
            if (mapping[s[i]] == mx) {
                res += s[i];
                mapping[s[i]]--;
            }
        }

        reverse(res.begin(), res.end());
        return res;
    }
};