Today I have done leetcode's June LeetCoding Challenge with cpp.

June LeetCoding Challenge 7

Description

Lexicographically Minimum String After Removing Stars

You are given a string s. It may contain any number of '*' characters. Your task is to remove all '*' characters.

While there is a '*', do the following operation:

• Delete the leftmost '*' and the smallest non-'*' character to its left. If there are several smallest characters, you can delete any of them.

Return the lexicographically smallest resulting string after removing all '*' characters.

Example 1:

Example 2:

Constraints:

• 1 <= s.length <= 105
• s consists only of lowercase English letters and '*'.
• The input is generated such that it is possible to delete all '*' characters.

Solution

template<typename T>
std::ostream& operator<<(std::ostream &out, const std::vector<T> &v) {
  if(v.size() == 0) {
    out << "[]" << std::endl;
    return out;
  }
  out << '[' << v[0];
  for(int i = 1; i < v.size(); ++i) {
    out << ", " << v[i];
  }
  out << ']';
  return out;
}
class Solution {
public:
  string clearStars(string s) {
    map<char, vector<int>> charPositions;
    int len = s.length();
    for(int i = 0; i < len; ++i) {
      if(isalpha(s[i])) {
        charPositions[s[i]].push_back(i);
      } else {
        char target = charPositions.begin()->first;
        charPositions[target].pop_back();
        if(charPositions[target].empty()) {
          charPositions.erase(target);
        }
      }
    }
    vector<int> result;
    for(auto [c, positions] : charPositions) {
      for(auto pos : positions) {
        result.push_back(1000 * pos + c);
      }
    }
    // cout << result << endl;
    sort(result.begin(), result.end());
    string answer(result.size(), ' ');
    for(int i = 0; i < result.size(); ++i) {
      answer[i] = result[i] % 1000;
    }
    return answer;
  }
};

// Accepted
// 602/602 cases passed (279 ms)
// Your runtime beats 19.94 % of cpp submissions
// Your memory usage beats 14.04 % of cpp submissions (112.3 MB)