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.
1#include <iostream>
2#include <stack>
3using namespace std;
4
5string removeStars(string s) {
6 string result;
7 for (char c : s) {
8 if (c == '*') {
9 if (!result.empty()) result.pop_back();
10 } else {
11 result.push_back(c);
12 }
13 }
14 return result;
15}
16
17int main() {
18 string s = "leet**cod*e";
19 cout << removeStars(s) << endl;
20 return 0;
21}In C++, we use a string as a dynamic stack-like structure. We pop_back the last character when a star is encountered, simulating the stack logic efficiently.
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.