Skip to content

3170. Lexicographically Minimum String After Removing Stars 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  string clearStars(string s) {
    string ans = s;
    vector<vector<int>> buckets(26);

    for (int i = 0; i < s.length(); ++i)
      if (s[i] == '*') {
        ans[i] = ' ';
        int j = 0;
        while (buckets[j].empty())
          ++j;
        ans[buckets[j].back()] = ' ', buckets[j].pop_back();
      } else {
        buckets[s[i] - 'a'].push_back(i);
      }

    std::erase(ans, ' ');
    return ans;
  }
};

 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 clearStars(String s) {
    StringBuilder sb = new StringBuilder(s);
    List<Integer>[] buckets = new List[26];

    for (int i = 0; i < 26; ++i)
      buckets[i] = new ArrayList<>();

    for (int i = 0; i < s.length(); ++i)
      if (s.charAt(i) == '*') {
        sb.setCharAt(i, ' ');
        int j = 0;
        while (buckets[j].isEmpty())
          ++j;
        sb.setCharAt(buckets[j].remove(buckets[j].size() - 1), ' ');
      } else {
        buckets[s.charAt(i) - 'a'].add(i);
      }

    return sb.toString().replaceAll(" ", "");
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def clearStars(self, s: str) -> str:
    ans = list(s)
    buckets = [[] for _ in range(26)]

    for i, c in enumerate(s):
      if c == '*':
        ans[i] = ''
        j = next(j for j, bucket in enumerate(buckets) if bucket)
        ans[buckets[j].pop()] = ''
      else:
        buckets[string.ascii_lowercase.index(c)].append(i)

    return ''.join(ans)