LF.82.Remove Adjacent Repeated Characters IV

Repeatedly remove all adjacent, repeated characters in a given string from left to right.

No adjacent characters should be identified in the final string.

Examples

"abbbaaccz" → "aaaccz" → "ccz" → "z"
"aabccdc" → "bccdc" → "bdc"

方法1，用stack 

public String deDup(String input) {
        // Write your solution here
        if (input == null){
            return null ;
        }
        if (input.length() == 0){
            return input;
        }
        //use a stack to store the visited value, if repeat then pop
        Deque<Character> stack = new LinkedList<>() ;
        stack.push(input.charAt(0));
        for (int i = 0; i < input.length() ; ) {
            if (stack.size() == 0){
                stack.push(input.charAt(i));
                i++;
                continue;
            }
            if (stack.size() > 0 && stack.peek() != input.charAt(i) ){
                stack.push(input.charAt(i));
                i++;
            } else if (stack.peek() == input.charAt(i)){
                // stack contains [a,b] b on top
                Character value = stack.peek() ;
                //skip all the b
                while (i<input.length() && input.charAt(i) == value){
                    i++ ;
                }
                stack.pop();
            }
        }
        char[] res = new char[stack.size()] ;
        for (int i = stack.size()-1; i >=0 ; i--) {
            res[i] = stack.pop() ;
        }
        return new String(res) ;
    }

方法2， 不用stack 通过控制指针来做到

 public String deDup_noStack(String input) {
        // Write your solution here
        if (input == null){
            return null ;
        }
        if (input.length() <= 1){
            return input;
        }
        //use a stack to store the visited value, if repeat then pop
        char[] chars = input.toCharArray();
        /*
        instead of using a extra stack explicitly, we can actually
        reuse the left side of the original char[] as the "stack"
        end(including) serves as the stack to be kept
        * */
        //
        int end = 0 ;
        for (int i = 1; i < chars.length; i++) {
            //if the stack is empty or no dup.
            if (end == -1 || chars[end] != chars[i]){
                chars[++end] = chars[i];
            } else{
                //otherwise, we need pop the top element by end--
                //and ignore all the consecutive duplicate chars.
                end--;
                //whenever you use i+1, check out of boundary
                while (i+1< chars.length && chars[i] == chars[i+1]){
                    i++;//i正好停在最后一个重复的位置上，然后i++ 去下一个非重复的元素
                }
            }
        }
        //end is index, count is length
        return new String(chars, 0 , end+1) ;
    }