3170. Lexicographically Minimum String After Removing Stars

Description

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 resulting string after removing all '*' characters.

 

Example 1:

Input: s = "aaba*"

Output: "aab"

Explanation:

We should delete one of the 'a' characters with '*'. If we choose s[3], s becomes the lexicographically smallest.

Example 2:

Input: s = "abc"

Output: "abc"

Explanation:

There is no '*' in the string.

 

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.

 

Solutions

Solution: Greedy

• Time complexity: O(26n -> n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {string} s
 * @return {string}
 */
const clearStars = function (s) {
  const BASE_CODE = 'a'.charCodeAt(0);
  const n = s.length;
  const letters = Array.from({ length: 26 }, () => []);
  const result = s.split('');

  for (let index = 0; index < n; index++) {
    const current = s[index];

    if (current === '*') {
      const indices = letters.find(indices => indices.length);
      const deleteIndex = indices.pop();

      result[index] = '';
      result[deleteIndex] = '';
    } else {
      const code = current.charCodeAt(0) - BASE_CODE;

      letters[code].push(index);
    }
  }

  return result.join('');
};