3170. Lexicographically Minimum String After Removing Stars LeetCode Solution
In this guide, you will get 3170. Lexicographically Minimum String After Removing Stars LeetCode Solution with the best time and space complexity. The solution to Lexicographically Minimum String After Removing Stars problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Lexicographically Minimum String After Removing Stars
You are given a string s. It may contain any number of ‘*’ characters. Your task is to remove all ‘*’ characters.
While there is a ‘*’, do the following operation:
Delete the leftmost ‘*’ and the smallest non-‘*’ character to its left. If there are several smallest characters, you can delete any of them.
Return the lexicographically smallest resulting string after removing all ‘*’ characters.
Example 1:
Input: s = “aaba*”
Output: “aab”
Explanation:
We should delete one of the ‘a’ characters with ‘*’. If we choose s[3], s becomes the lexicographically smallest.
Example 2:
Input: s = “abc”
Output: “abc”
Explanation:
There is no ‘*’ in the string.
Constraints:
1 <= s.length <= 105
s consists only of lowercase English letters and '*'.
The input is generated such that it is possible to delete all '*' characters.
3170. Lexicographically Minimum String After Removing Stars LeetCode Solution in C++
class Solution {
public:
string clearStars(string s) {
string ans = s;
vector<vector<int>> buckets(26);
for (int i = 0; i < s.length(); ++i)
if (s[i] == '*') {
ans[i] = ' ';
int j = 0;
while (buckets[j].empty())
++j;
ans[buckets[j].back()] = ' ', buckets[j].pop_back();
} else {
buckets[s[i] - 'a'].push_back(i);
}
std::erase(ans, ' ');
return ans;
}
}; /* code provided by PROGIEZ */
3170. Lexicographically Minimum String After Removing Stars LeetCode Solution in Java
class Solution {
public String clearStars(String s) {
StringBuilder sb = new StringBuilder(s);
List<Integer>[] buckets = new List[26];
for (int i = 0; i < 26; ++i)
buckets[i] = new ArrayList<>();
for (int i = 0; i < s.length(); ++i)
if (s.charAt(i) == '*') {
sb.setCharAt(i, ' ');
int j = 0;
while (buckets[j].isEmpty())
++j;
sb.setCharAt(buckets[j].remove(buckets[j].size() - 1), ' ');
} else {
buckets[s.charAt(i) - 'a'].add(i);
}
return sb.toString().replaceAll(" ", "");
}
} // code provided by PROGIEZ
3170. Lexicographically Minimum String After Removing Stars LeetCode Solution in Python
class Solution:
def clearStars(self, s: str) -> str:
ans = list(s)
buckets = [[] for _ in range(26)]
for i, c in enumerate(s):
if c == '*':
ans[i] = ''
j = next(j for j, bucket in enumerate(buckets) if bucket)
ans[buckets[j].pop()] = ''
else:
buckets[ord(c) - ord('a')].append(i)
return ''.join(ans) # code by PROGIEZ
