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.
1function removeStars(s) {
2 const result = [];
3 for (const char of s) {
4 if (char === '*') {
5 if (result.length) result.pop();
6 } else {
7 result.push(char);
8 }
9 }
10 return result.join('');
11}
12
13console.log(removeStars("leet**cod*e"));In JavaScript, an array is used to simulate stack operations. The pop method handles the removal of the last character upon encountering a star.
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.
public class Program {
public static string RemoveStars(string s) {
char[] arr = s.ToCharArray();
int write = 0;
for (int read = 0; read < arr.Length; ++read) {
if (arr[read] == '*') {
if (write > 0) --write;
} else {
arr[write++] = arr[read];
}
}
return new string(arr, 0, write);
}
public static void Main() {
Console.WriteLine(RemoveStars("leet**cod*e"));
}
}In C#, a character array is manipulated with read and write positions to enable efficient in-place writing.