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, 2, 3, 3, 3, 2, 2} → {1, 2, 2, 2} → {1}, return {1}

Solution 1: 用stack (stringbuilder)

  public String deDup(String input) {
    if (input == null || input.length() < 2) {
      return input;
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < input.length(); i++) {
      char c = input.charAt(i);
      if (sb.length() == 0 || c != sb.charAt(sb.length() - 1)) {
        sb.append(c);
      } else if (i + 1 < input.length() && input.charAt(i + 1) == c) {  //不能缺少这
        continue;
      } else if (c == sb.charAt(sb.length() - 1)) {
        sb.deleteCharAt(sb.length() - 1);
      }
    }

    return sb.toString();
  }

Solution 2: in place，two pointers

  public int[] dedup(int[] array) {
    if (array.length < 2) {
      return array;
    }
    int slow = 0; //exclude slow。注意fast从0开始，与slow - 1比较
    for (int fast = 0; fast < array.length; fast++) {
      if (slow == 0 || array[fast] != array[slow - 1]) {
        array[slow] = array[fast];
        slow++;
      } else if (fast + 1 < array.length && array[fast + 1] == array[fast]) {  //不能缺少这
        continue;
      } else if (array[fast] == array[slow - 1]){
        slow--; //类似于stack pop
      }
    }
    return Arrays.copyOf(array, slow);
  }