LeetCode //C - 2390. Removing Stars From a String

2390. Removing Stars From a String

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**code". s becomes "leecod*e”.
• The closest character to the 2nd star is ‘e’ in “leecode”. 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<=10^5$
• s consists of lowercase English letters and stars *.
• The operation above can be performed on s.

From: LeetCode
Link: 2390. Removing Stars From a String

---

Solution:

Ideas：

1. Initialize a Stack: A character array (acting as a stack) is created to temporarily store characters from the input string.

2. Process the Input String: Iterate through each character of the input string s.

   • If the current character is not an asterisk (*), it is pushed onto the stack. This is akin to adding elements to a list, where you are keeping track of the elements in their original order (minus the asterisks and the characters to be removed).
   • If the current character is an asterisk, it indicates that the previous non-asterisk character (the character on the top of the stack) should be removed. This is done by simply moving the stack pointer down, effectively ‘popping’ the top character.

3. Form the Resultant String: After processing all characters of s, the stack contains the resultant string, but in reverse order. The characters in the stack are then copied into a new string called result, which represents the final string after all removals.

4. Memory Management: Dynamic memory allocation is used for the stack and the result string. It’s important to allocate enough memory to accommodate all characters and the null terminator. After copying the required characters to the result, the memory used by the stack is freed to prevent memory leaks.

5. Return the Result: Finally, the function returns the result string, which is the modified version of the input string after performing all the specified operations.

Code:

char* removeStars(char* s) {
    int n = strlen(s);  // Length of the input string
    char* stack = (char*)malloc((n + 1) * sizeof(char));  // Allocate memory for the stack, +1 for null terminator
    int top = -1;  // Top of the stack

    // Traverse the input string
    for (int i = 0; i < n; i++) {
        if (s[i] != '*') {
            // Push non-star characters onto the stack
            stack[++top] = s[i];
        } else if (top != -1) {
            // Pop the top character for a star
            top--;
        }
    }

    // Add a null terminator at the end of the stack content
    stack[top + 1] = '\0';

    // Create the result string with exact size
    char* result = (char*)malloc((strlen(stack) + 1) * sizeof(char));  // Allocate memory for the result based on stack's current length
    for (int i = 0; i <= top; i++) {
        result[i] = stack[i];  // Manually copy the characters
    }
    result[top + 1] = '\0';  // Add null terminator to the result

    free(stack);  // Free the stack memory
    return result;  // Return the result
}