Remove Chars from String in place

Remove given characters in input string, the relative order of other characters should be remained. Return the new string after deletion.

Assumptions

• The given input string is not null.

• The characters to be removed is given by another string, it is guaranteed to be not null.

Examples

• input = "abcd", t = "ab", delete all instances of 'a' and 'b', the result is "cd".

Solution: HashSet and fast slow pointer

  private Set<Character> makeSet (String t) {
    Set<Character> set = new HashSet<Character>();
    for (int i = 0; i < t.length(); i++) {
      set.add(t.charAt(i));
    }
    return set;
  }
  public String remove(String input, String t) {
    //get input into array
    char[] array = input.toChararray();
    Set<Character> set = makeSet(t);

    //slow: 0 -> slow not inclusive is result array
    //fast: swap with slow if kept
    int slow = 0;
    for (int fast = 0; fast < array.length; fast++) {
      if (!set.contains(array[fast])) {
        array[slow++] = array[fast];
      }
    }
    
    return new String(array, 0, slow);
  }

Time Comp:

O(t) convert to set.

O(traverse input) * O(1) access set

O(t + N)

Space Comp: O(t)