Sponsored
Sponsored
This approach utilizes a stack data structure to handle the character removals efficiently. As we iterate through the string, whenever a star (*) is encountered, we pop from the stack, effectively removing the last non-star character added. This allows us to handle both the star and its preceding non-star character in O(1) time.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), for the stack to hold characters.
1using System;
2using System.Text;
3
4public class Program {
5 public static string RemoveStars(string s) {
6 StringBuilder result = new StringBuilder();
7 foreach (char c in s) {
8 if (c == '*') {
9 if (result.Length > 0) result.Remove(result.Length - 1, 1);
10 } else {
11 result.Append(c);
12 }
13 }
14 return result.ToString();
15 }
16
17 public static void Main() {
18 Console.WriteLine(RemoveStars("leet**cod*e"));
19 }
20}For C#, a StringBuilder is utilized, and we Remove the last character when a star is detected, functioning similarly to a stack.
This alternative method involves using a simple two-pointer technique where we iterate through the string and build the result in place. We treat the string as a writable array and maintain a 'write' index that tells us where to place the next character. When we encounter a star, we just need to move the 'write' index back to overwrite the previous character.
Time Complexity: O(n)
Space Complexity: O(1), since operations are done in-place.
1
This Python solution effectively modifies the list of characters in place using two indices, read and write.