2
$\begingroup$

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?

$\endgroup$
4
  • 2
    $\begingroup$ You said "... I managed to find the following solution...", but it's not in your post. Please incldue your solution with some details as to why it does not meet the requirements $\endgroup$
    – Russel
    May 13 at 11:18
  • $\begingroup$ I'm not sure this is possible. Consider a string of the form $a^{n/2}w$, where $w \in (bc+bbc)^*$ has length $n/2$. There are exponentially many possible strings $w$. You need to convert $a^{n/2}w$ to $w0^{n/2}$ in time $O(n)$ on a single-tape Turing machine. In particular, $\Omega(n)$ bits of information need to pass from the right half of the tape to the left quarter of the tape, passing through $n/4$ positions. This requires $\Omega(n^2)$ time. $\endgroup$ May 13 at 12:07
  • 1
    $\begingroup$ @YuvalFilmus, I don't think he is restricting the problem to TM? $\endgroup$
    – Russel
    May 13 at 13:23
  • $\begingroup$ Do you consider the possibility of producing repeated strings after deletion? For example if the string is "abbbaa", then deleting the "bbb" substring will produce "aaa", which should be removed also. Is that possible in your problem? $\endgroup$
    – Russel
    May 13 at 13:51

2 Answers 2

1
$\begingroup$

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
$\endgroup$
1
$\begingroup$

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)$.
$\endgroup$
10
  • $\begingroup$ Thanks! I didn't understand how it should work in case there is a deletable string after another deleteable string? $\endgroup$
    – chucha
    May 13 at 14:09
  • $\begingroup$ @chucha, the idea is to find the maximal deletable string, so there will be no two consecutive deletable string, because those two will be combined as one. While we are at it, I have asked in the comment above if you will consider the possibility of producing repeated strings after deletion? For example if the string is "abbbaa", then deleting the "bbb" substring will produce "aaa", which should be removed also. Is that possible in your problem? $\endgroup$
    – Russel
    May 13 at 14:13
  • $\begingroup$ "which should be removed also" - The fact that you asked about it shows that you don't actually know that. $\endgroup$ May 13 at 14:30
  • $\begingroup$ @KellyBundy, sorry, but I did not understand your comment. Care to explain? I was asking about the scenario since my solution does not take that into consideration. This scenario was not discussed in the post, so I would like some clarification just in case I need to make corrections, if I can actually make amends, or delete my solution entirely. If this scenario does not matter then, my solution might stay as it. $\endgroup$
    – Russel
    May 13 at 14:35
  • 1
    $\begingroup$ For example, what about "abbbaaab"? In such a case, the exact process matters. You could go "abbbaaab"=>"aaaab"=>"b" or "abbbaaab"=>"abbbb"=>"a" or "abbbaaab"=>"ab". The question would absolutely have to specify precisely how to do it. Since it doesn't, I must assume that it doesn't want us to remove triples we create ourselves. $\endgroup$ May 13 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.