RemoveAdjacentRepeatedCharactersI

Remove Adjacent Repeated Characters I

https://app.laicode.io/app/problem/79

Description

Remove adjacent, repeated characters in a given string, leaving only one character for each group of such characters.

Assumptions

• Try to do it in place.

Examples

• "aaaabbbc" is transferred to "abc"

Corner Cases

• If the given string is null, we do not need to do anything.

Easy

Array

String

Assumption

The input string cannot be null or empty. And by converting the string to a char array, we assume that we are doing the operations in-place.

Algorithm

This question is similar to Array Deduplication I

We use two pointers:

1. All the characters to the left of the slow pointer, including the one pointed to by the slow pointer, are the ones that have been processed and kept for result
2. All the characters to the right of the right pointer are the ones that we are about to check
3. All the characters in the middle of the two pointers are the ones that have already been processed, but we are not interested in them in terms of the result

When iterating over the string:

1. When we see duplicate characters, skip the fast pointer.
2. When we see different characters, copy input[fast] to input[slow] such that input[0, slow] are all kept to return. And we increment the slow pointer, moving into the "useless" section.

Solution

Code

public class Solution {
    public String deDup(String input) {
        // Write your solution here
        if (input == null || input.length() < 2) {
            return input;
        }
        char[] array = input.toCharArray();
        int slow = 0;
        for (int fast = 1; fast < array.length; fast++) {
            if (array[fast] != array[slow]) {
                array[++slow] = array[fast];
            }
        }
        // All the chars to the left of slow, including slow ⇒ result
        return new String(array, 0, slow + 1);
    }
}

Complexity

Time: one iteration over the string ⇒ O(n)

Space: a char array of size n ⇒ O(n). But we could consider this is in-place.