Skip to content

Instantly share code, notes, and snippets.

@ritik-agrawal
Created February 10, 2024 07:54
Show Gist options
  • Save ritik-agrawal/c0069d1a0093909f18f64b996b701ab8 to your computer and use it in GitHub Desktop.
Save ritik-agrawal/c0069d1a0093909f18f64b996b701ab8 to your computer and use it in GitHub Desktop.
class Solution {
public String removeStars(String s) {
var stk = new ArrayList<Character>();
var len = s.length();
for (int i = 0; i < len; i++){
var ch = s.charAt(i);
if (Objects.equals(ch, '*')){
pop(stk);
} else {
stk.add(ch);
}
}
return getValue(stk);
}
private void pop(List<Character> stk){
if (stk.size() > 0){
stk.remove(stk.size()-1);
}
}
private String getValue(List<Character> stk){
var retVal = new StringBuilder();
var len = stk.size();
for (Character i : stk){
retVal.append(i);
}
//System.out.println("Result:"+ retVal.toString());
return retVal.toString();
}
}
@ritik-agrawal
Copy link
Author

Leetcode

Question link: https://leetcode.com/problems/removing-stars-from-a-string/description/

Achievement

  • The above code has a runtime of 49ms which beats 70% of the total code submissions.
  • The code uses stack logic to solve the problem
  • The above solution is not the best solution

@ritik-agrawal
Copy link
Author

Best Solution

  • The Below code beats 100% of the cases with a runtime of 11ms.
  • This uses byteArray and basic math logic to resolve the problem
  • for 1 star 2 characters are deleted. and so gets the count of stars and when encounters the non-star character shifts the current value to the index as given by (i - stars *2) function.
class Solution {
    public String removeStars(String s) {
        int len = s.length();
        byte[] result = new byte[len];
        s.getBytes(0, len, result, 0);
        int stars = 0;
        for (int i = 0; i < len; i++) {
            if (result[i] == '*') {
                stars++;
            } else {
                result[i - stars * 2] = result[i];
            }
        }
        return new String(result, 0, len - stars * 2);
    }
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment