removeStars.java

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();
    }

}

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

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);
    }
}