Using Finite-State Machine (FSM) to model and solve string problems - Part II

We use FSM to model when we're inside stars or outside, keep track of the count of stars, and manipulate an index of the final string. Avoid string manipulation, it will lead to time-limit-exceeded. Instead, keep track of the index and use a StringBuilder which allows you to modify each cell in place, only switching back to string at the very last step. Code is down below, cheers, ACC.

Removing Stars From a String - LeetCode

2390. Removing Stars From a String

Medium

You are given a string s, which contains stars *.

In one operation, you can:

• Choose a star in s.
• Remove the closest non-star character to its left, as well as remove the star itself.

Return the string after all stars have been removed.

Note:

• The input will be generated such that the operation is always possible.
• It can be shown that the resulting string will always be unique.

 

Example 1:

Input: s = "leet**cod*e"
Output: "lecoe"
Explanation: Performing the removals from left to right:
- The closest character to the 1st star is 't' in "leet**cod*e". s becomes "lee*cod*e".
- The closest character to the 2nd star is 'e' in "lee*cod*e". s becomes "lecod*e".
- The closest character to the 3rd star is 'd' in "lecod*e". s becomes "lecoe".
There are no more stars, so we return "lecoe".

Example 2:

Input: s = "erase*****"
Output: ""
Explanation: The entire string is removed, so we return an empty string.

 

Constraints:

• 1 <= s.length <= 105
• s consists of lowercase English letters and stars *.
• The operation above can be performed on s.

Accepted

16,712

Submissions

28,031

public string RemoveStars(string s)
{
    bool insideStars = false;
    StringBuilder retVal = new StringBuilder(s);
    int index = 0;
    int countStars = 0;

    for (int i = 0; i < s.Length; i++)
    {
        if (s[i] == '*')
        {
            insideStars = true;
            countStars++;
        }
        else
        {
            if (insideStars)
            {
                index -= countStars;
                if (index < 0) index = 0;
            }
            insideStars = false;
            countStars = 0;
            retVal[index++] = s[i];
        }
    }

    if (insideStars)
    {
        index -= countStars;
        if (index < 0) index = 0;
    }

    if (index == 0) return "";
    return retVal.ToString().Substring(0, index);
}