algorithm - 如何理解hackerrank中某道题的具体解法？

Question

这是关于 hackerrand 中一个问题的解决方案。请点击链接:

the link of problem description

string reverseShuffleMerge(string s) {
int n = s.length();
vector<char> sarr(s.rbegin(), s.rend());
int alpha_size = 26;
vector<int> freq(alpha_size, 0);
for (int i = 0; i < n; i++) {
    freq[sarr[i] - 'a']++;
}
vector<int> did_use(alpha_size, 0);
vector<int> can_use(freq.begin(), freq.end());
vector<char> A;
for (int i = 0; i < n; i++) {
    if (did_use[sarr[i] - 'a'] < freq[sarr[i] - 'a'] / 2) {
        while (A.size() > 0 && sarr[i] < A.back() 
               && did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 
               >= freq[A.back() - 'a'] / 2) {
            did_use[A.back() - 'a']--;
            A.pop_back();
        }
        A.push_back(sarr[i]);
        did_use[sarr[i] - 'a']++;
        can_use[sarr[i] - 'a']--;
    } else {
        can_use[sarr[i] - 'a']--;
    }
}
return string(A.begin(), A.end());

我不明白这一行的要点:did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a']/2

谁能帮助阐明这条线在解决方案中扮演的角色？

Answer 1

在这道题中，字符串s中所有字符出现的频率都是偶数。答案将包含这些字符的一半。例如，如果 s="aaaabbcc"，则答案必须包含 2 a、1 b 和 1 c。

所以 did_use[A.back() - 'a'] + can_use[A.back() - 'a'] - 1 >= freq[A.back() - 'a']/2 这是为了如果我们删除 A.back() 字符，我们可以在以后添加/制作所需数量的 A.back() 字符吗？字符串。