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.
1import java.util.*;
2
3public class RemoveStars {
4 public static String removeStars(String s) {
5 StringBuilder result = new StringBuilder();
6 for (char c : s.toCharArray()) {
7 if (c == '*') {
8 if (result.length() > 0) result.deleteCharAt(result.length() - 1);
9 } else {
10 result.append(c);
11 }
12 }
13 return result.toString();
14 }
15
16 public static void main(String[] args) {
17 String s = "leet**cod*e";
18 System.out.println(removeStars(s));
19 }
20}In Java, a StringBuilder acts as our stack. We deleteCharAt the last position for each star, ensuring the closest left character is removed.
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.
1
This Python solution effectively modifies the list of characters in place using two indices, read and write.