2390_RemovingStarsFromaString

---

title: 2390. Removing Stars From a String tags: - stack - Two pointers categories: leetcode comments: false

problem

solution

class Solution {
public:
    string removeStars(string s) {
        stack<char> sta;
        int n = s.size();
        for(char c:s){
            if(c!= '*') sta.push(c);
            else sta.pop();
        }
        string ret;
        while(!sta.empty()){
            ret+=sta.top();
            sta.pop();
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

class Solution {
public:
    string removeStars(string s) {
        string ret;
        int l= 0, n=s.size(), r=n-1;
        while(r>-1){
            if(s[r] == '*'){
                l++;
            }
            else if(s[r]){
                if(l==0) ret+=s[r];
                else if(l>0) l--;
            }
            r--;
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

analysis

• time complexity O(n)
• space complexity O(n) -> O(1)