Dare2Solve
Given a string s
that consists of characters and stars ('*'
), the task is to remove the characters that are immediately before each star. Each '*'
can only remove the preceding character, and once removed, it is no longer part of the string. Return the final string after performing all the operations.
The problem can be intuitively solved by thinking of the '*'
characters as backspaces. Each star deletes the last added character, so a stack or stack-like approach will help us efficiently simulate this process.
Iteration and Stack Mechanism:
'*'
, remove the last character from the stack or result.Implementation Details:
StringBuilder
in Java or a string
in C++ to efficiently add and remove characters.O(n), where n
is the length of the string s
. We iterate through each character once.
O(n), in the worst case, where n
characters could be stored in the stack or result if there are no stars.
class Solution {
public:
string removeStars(string s) {
string result;
for (char c : s) {
if (c == '*') {
if (!result.empty()) {
result.pop_back();
}
} else {
result.push_back(c);
}
}
return result;
}
};
class Solution:
def removeStars(self, s: str) -> str:
self.ctr = 0
return self.recurse(s, 0)
def recurse(self, s: str, i: int) -> str:
if i >= len(s):
return ""
result = self.recurse(s, i + 1)
if s[i] == '*':
self.ctr += 1
return result
elif self.ctr > 0:
self.ctr -= 1
return result
else:
return s[i] + result
class Solution {
public String removeStars(String s) {
StringBuilder result = new StringBuilder();
for (char c : s.toCharArray()) {
if (c == '*') {
if (result.length() > 0) {
result.deleteCharAt(result.length() - 1);
}
} else {
result.append(c);
}
}
return result.toString();
}
}
var removeStars = function (s) {
let ctr = 0;
return (function recurse(i) {
if (!s[i]) return "";
const result = recurse(i + 1);
if (s[i] == '*') {
ctr++;
return result
} else if (ctr) {
ctr--;
return result;
} else return s[i] + result;
})(0);
};