Here, we will learn about how to solve removing Stars From a String problem of leet code 2390 with code and algorithm.
You are given a string str which contains stars * and characters.
In one operation, you can:
- Choose a star in str.
- Remove the closest non-star character to its left, as well as remove the star itself.
Return the string after all stars have been removed.
Example:
Input: str = "techie**ind*r" Output: "techinr" Input: str = "erase*****" Output: "" Input: str = "abb*cdfg*****x*" Output: "a" Input: str = "aaaa****a" Output: "a"
Explanation:
If you look at closely, for each star we remove one closest character towards left side of star.
Algorithm 1:
- Iterate over string from left to right
- Take one tmp variable of string type
- If you find “*” during iteration, then remove the one character from back in tmp string variable
- If you find any “character” during iteration then add this to tmp string variable
- return tmp variable string
Removing Stars From a String code in C++
Code 1:
#include <iostream>
#include <algorithm>
using namespace std;
string removeStars(string s) {
string tmp = "";
// Iterate over input string
for(auto &ch : s) {
if(ch == '*') {
// Remove character from back
tmp.pop_back();
} else {
// add character to back
tmp.push_back(ch);
}
}
return tmp;
}
int main()
{
cout<<removeStars("abb*cdfg*****x*");
return 0;
}Output:
a
Code 2:
#include <iostream>
#include <algorithm>
using namespace std;
string removeStars(string s) {
string tmp = "";
int count = 0;
int size = s.length() - 1;
while(size >= 0) {
if(s[size] == '*') {
count++;
} else {
if(count == 0) {
tmp += s[size];
} else {
count--;
}
}
size--;
}
reverse(tmp.begin(), tmp.end());
return tmp;
}
int main()
{
cout<<removeStars("abb*cdfg***x*");
return 0;
}Output:
abc
To check more leetcode problem’s solution. Pls click given below link:
https://www.techieindoor.com/category/leetcode/