Scale Engineer

Lexicographically Minimum String After Removing Stars

Med
#2816Time: O(N^2), where N is the length of the string. In each of the O(N) iterations (one for each star), finding the star, the smallest character, and its position takes O(N) time. Deletion in a `StringBuilder` also takes O(N).Space: O(N), where N is the length of the string, for storing the `StringBuilder`.1 company
Patterns
Greedy
Data structures
Hash TableStringStackHeap (Priority Queue)
Companies
Flexera

Prompt

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:

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.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. It repeatedly finds the leftmost star, identifies the character to be removed based on the greedy strategy, and reconstructs the string. This process continues until no stars are left.

Algorithm

  • Convert the input string s to a mutable StringBuilder.
  • Loop as long as a '*' character exists in the StringBuilder.
    • Find the index of the leftmost '*'. Let this be starIndex.
    • If no star is found, exit the loop.
    • Find the smallest character in the substring to the left of the star (0 to starIndex - 1).
    • Find the rightmost index (removeIndex) of this smallest character in the same left-side substring.
    • Delete the character at starIndex first, then the character at removeIndex.
  • Convert the StringBuilder back to a string and return it.

Walkthrough

In this brute-force method, we use a mutable string representation, like Java's StringBuilder, to allow for efficient character deletions. We enter a loop that continues as long as there are '*' characters in the string. In each iteration, we locate the first '*'. Then, we scan all characters to its left to determine the smallest character. To get the lexicographically smallest final string, we must remove the rightmost occurrence of this smallest character. So, we perform a reverse scan from the star's position to find its index. Finally, we delete both the star and the identified character. This is repeated until all stars are processed.

class Solution {    public String clearStars(String s) {        StringBuilder sb = new StringBuilder(s);        while (true) {            int starIndex = sb.indexOf("*");            if (starIndex == -1) {                break;            }             char smallestChar = Character.MAX_VALUE;            int removeIndex = -1;             // Find the smallest character to the left of the star            for (int i = 0; i < starIndex; i++) {                if (sb.charAt(i) != '*') {                    smallestChar = (char) Math.min(smallestChar, sb.charAt(i));                }            }             // Find the rightmost occurrence of that smallest character            for (int i = starIndex - 1; i >= 0; i--) {                if (sb.charAt(i) == smallestChar) {                    removeIndex = i;                    break;                }            }                        // Delete star first (larger index) to not affect smaller index            sb.deleteCharAt(starIndex);            if (removeIndex != -1) {                sb.deleteCharAt(removeIndex);            }        }        return sb.toString();    }}

Complexity

Time

O(N^2), where N is the length of the string. In each of the O(N) iterations (one for each star), finding the star, the smallest character, and its position takes O(N) time. Deletion in a `StringBuilder` also takes O(N).

Space

O(N), where N is the length of the string, for storing the `StringBuilder`.

Trade-offs

Pros

  • Conceptually simple and easy to follow the problem's description.

Cons

  • Highly inefficient due to repeated scanning and modification of the string.

  • Will likely result in a 'Time Limit Exceeded' error for large inputs.

Solutions

public class Solution {    public string ClearStars(string s) {        int n = s.Length;        List < int > [] g = new List < int > [26];        for (int i = 0; i < 26; i++) {            g[i] = new List < int > ();        }        bool[] rem = new bool[n];        for (int i = 0; i < n; i++) {            char ch = s[i];            if (ch == '*') {                rem[i] = true;                for (int j = 0; j < 26; j++) {                    if (g[j].Count > 0) {                        int idx = g[j][g[j].Count - 1];                        g[j].RemoveAt(g[j].Count - 1);                        rem[idx] = true;                        break;                    }                }            } else {                g[ch - 'a'].Add(i);            }        }        var ans = new System.Text.StringBuilder();        for (int i = 0; i < n; i++) {            if (!rem[i]) {                ans.Append(s[i]);            }        }        return ans.ToString();    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem