Removing Stars From a String in Python – LeetCode75 Clearly Explained

by

The Removing Stars From a String problem from LeetCode75 is a common interview-style string manipulation challenge that tests both logical reasoning and efficient use of data structures. At its core, the problem teaches you how to simulate backspace operations efficiently using a stack, making it an excellent exercise for understanding how Last-In-First-Out (LIFO) structures work in real scenarios.

Removing Stars From a String in Python – LeetCode75 Explained

This blog will walk you through the problem statement, examples, and a complete Python solution with a detailed step-by-step explanation.

Problem Statement

You are given a string s containing lowercase English letters and the character *.

When you see a *:

  1. Remove the * itself.
  2. Remove the closest non-star character to its left.

Return the final string after all operations.

Understanding the Problem

Think of * as a backspace key in a text editor:

  • Typing letters → they get added.
  • Pressing * → deletes the most recent character.

A stack works perfectly here because it follows Last In, First Out (LIFO).

Examples

Example 1

Input: s = "leet**cod*e"
Output: "lecoe"

Example 2

Input: s = "erase*****"
Output: ""

Example 3

Input: s = "ab*c*d"
Output: "d"

Complete Solution

class Solution:
    def removeStars(self, s: str) -> str:
        # Step 1: Initialize stack
        stack = []
        
        # Step 2: Traverse string
        for char in s:
            if char == '*':
                if stack:
                    stack.pop()
            else:
                stack.append(char)
        
        # Step 3: Construct result
        return ''.join(stack)

Python Solution – Step by Step

Step 1: Initialize a Stack

We need a stack (Python list) to store characters as we process them.

stack = []

Step 2: Traverse the String

For each character in s:

  • If it’s a letter → append it to stack.
  • If it’s * → pop the last character (if any).
for char in s:
    if char == '*':
        if stack:
            stack.pop()   # remove last added char
    else:
        stack.append(char)  # store valid char

Step 3: Construct the Result

Join everything left in the stack into the final string.

return ''.join(stack)

Why This Solution Works

  • Push to stack = typing a character.
  • Pop from stack = pressing backspace (*).
  • After processing all characters, the stack contains exactly what remains.

Time and Space Complexity

  • Time Complexity: O(n) → one pass through s.
  • Space Complexity: O(n) → worst-case stack usage.

Edge Cases

InputOutputExplanation
"a*"""a removed by *.
"***"""Only stars, nothing remains.
"abc""abc"No stars at all.
"ab**c""c"Stars delete a and b.

Real-World Applications

This problem mirrors text editing behavior:

  • Backspace in word processors.
  • Undo operations in apps.
  • Cleaning raw data where * is a deletion marker.

Conclusion

This problem highlights how stacks can simplify tricky string operations. By treating each * as a backspace, we simulate text editing behavior in a clean and efficient way. The solution runs in linear time, making it practical for large inputs while remaining easy to understand and implement.

More importantly, this problem teaches a structured way to approach string manipulation challenges. By breaking the task into storing characters, applying deletions, and reconstructing the result, we develop a clear problem-solving mindset. This skill is valuable not only for interviews but also for real-world applications like text editors, undo features, and data cleaning workflows.

References

LeetCode Problem Page – LeetCode 2390: Removing Stars From a String

GeeksforGeeks – Stack Data Structure – Stack in Python

Real Python – String Manipulation in Python – Python Strings Tutorial

Leave a Comment