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.
1def removeStars(s: str) -> str:
2 result = []
3 for c in s:
4 if c == '*':
5 if result:
6 result.pop()
7 else:
8 result.append(c)
9 return ''.join(result)
10
11s = "leet**cod*e"
12print(removeStars(s))In this Python solution, a list is used as a stack to keep track of non-star characters. We pop the last element on 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.
1using namespace std;
string removeStars(string s) {
int write = 0;
for (int read = 0; read < s.size(); ++read) {
if (s[read] == '*') {
if (write > 0) --write;
} else {
s[write++] = s[read];
}
}
return s.substr(0, write);
}
int main() {
string s = "leet**cod*e";
cout << removeStars(s) << endl;
return 0;
}Two pointers, read and write, are employed within the same string space, managing overwriting based on star occurrences.