Delete consecutive characters and add zeros at the end with a restriction

Question

Given an array of characters, I need to delete all the characters that got repeated 3 or more times (consecutively) and add '0' at the end of the array for every deleted character,

The restrictions:

• $O(n)$ time
• $O(1)$ memory
• Can't overwrite a cell in the array more than once

Examples: "aacccbbddde" --> "aabbe000000"

I managed to find the following solution without the restriction of $O(1)$ memory / overwrite (I can do only one at a time)

Any ideas?

Answer 1

Have a write index. Then go through the array, identify and measure each streak of equal characters. Streaks shorter than 3 get written. At the end, write zeros at the remaining indices.

Python implementation:

from itertools import groupby

array  = list("aacccbbddde")
expect = list("aabbe000000")

write = 0
for char, streak in groupby(array):
    length = sum(1 for _ in streak)
    if length < 3:
        for _ in range(length):
            array[write] = char
            write += 1
for write in range(write, len(array)):
    array[write] = '0'

print(array)
print(array == expect)

Output (Try it online!):

['a', 'a', 'b', 'b', 'e', '0', '0', '0', '0', '0', '0']
True

Answer 2

While waiting for your updated post that includes your solution, I have posted mine:

Solution

A substring is deletable if all its characters will be deleted based on your requirement. This substring may have several groups of repeated characters. For example, if the string is "accccbbbdddagggde" then "cccc" and "bbb" are deletables. A deletable substring is maximal if it is not adjacent to any deletable substring.The examples earlier are not maximal deletable substring, but "ccccbbbddd" and "ggg" are maximal. An undeletable substring is a substring that will remain in the string. A maximal undeletable substring follows the same idea as maximal deletable.

Your problem is essentially to remove all maximal deletable substring in a string, and then append the resulting string with as many 0 as the removed characters. Below is a solution:

1. Let $cur = -1$ be the starting index in the array that can be overwritten. Initially, there is no index to overwrite. Let $count$ be the number of characters that will be removed.

2. Scan the array until you find the left-most maximal deletable substring $d$. Let $d_{start}$ and $d_{end}$ be the start and end index of this string, and $d_{len} = |d|$ be $d$'s length.

3. Continue the scanning to find the maximal undeletable substring $u$ adjacent to $d$. Let $u_{start}$ and $u_{end}$ be its start and end indices and $u_{len} = |u|$ be $u$'s length.

4. If both $d$ and $u$ exist, do the following:

   • If $cur$ is still -1, set $cur = d_{start}$.
   • Set $count = count + d_{len}$.
   • Copy substring $u$ at position $cur$ all the way to $cur + u_{len} - 1$. This essentially moves substring $u$ to the left, overwriting $d$, entirely or partially, depending on whether $|u| \ge |d|$.
   • Move $cur$ passed the copied substring, that is let $cur = cur + u_{len}$.
   • Go back to step 2, but the scanning will start at $u_{end} + 1$.

5. If either $u$ or $d$ does not exist, write as many 0 $count$ to the array starting at position $cur$, and we are done.

Analysis

• This solution uses only $O(1)$ extra variables, hence it uses $O(1)$ extra space.
• It overwrites an index of the array once. Either at step 4, when moving an undeletable string to the left or when writing 0's at step 5.
• This solution runs in $O(n)$ time. Observe that an index is visited at most twice, once when it is considered in the search for deletable/undeletable substring and the other when it is overwritten. Finding a deletable and undeletable takes time $O(|d|)$ and $O(|u|)$ resp., while moving an undeletable takes $O(|d|)$ time. In the worst-case, all substrings in the string will be classified as is either deletable or undeletable. Since indices are written at most once, the total time of finding and moving all such substrings is $O(n)$.