CODEWITHSUNDEEP
algorithm
Gilmor
Gilmor

Reputation: 53

Deleting duplicate characters from array

Got asked this question in an interview and couldn't find a solution. Given an array of characters delete all the characters that got repeated k or more times consecutively and add '#' in the end of the array for every deleted character. Example:

"xavvvarrrt"->"xaat######"

O(1) memory and O(n) time without writing to the same cell twice.

The tricky part for me was that I am not allowed to overwrite a cell more than once, which means I need to know exactly where each character will move after deleting the duplicates. The best I could come up with is iterating once on the array and saving in a map the occurrences of each character, and when iterating again and checking if the current character is not deleted then move it to the new position according to the offset, if it is deleted then update an offset variable. The problem with this approach is that it won't work in this scenario: "aabbaa" because 'a' appears at two different places. So when I thought about saving an array of occurrences in the map but now it won't use O(1) memory.

Thanks

Upvotes: 2

Views: 125

Answers (2)

siracusa
siracusa

Reputation: 3650

Here is a version similar to the other JS answer, but a bit simpler:

function repl(str) {
    str = str.split("");
    var count = 1, write = 0;

    for (var read = 0; read < str.length; read++) {
        if (str[read] == str[read+1])
            count++;
        else {
            if (count < 3) {
                for (var i = 0; i < count; i++)
                    str[write++] = str[read];
            }
            count = 1;
        }
    }

    while (write < str.length)
        str[write++] = '#';

    return str.join("");
}

function demo(str) {
    console.log(str + " ==> " + repl(str));
}

demo("a");
demo("aa");
demo("aaa");
demo("aaaaaaa");
demo("aayyyycbbbee");
demo("xavvvarrrt");
demo("xxxaaaaxxxaaa");
demo("xxaavvvaarrrbbsssgggtt");

/*
Output:
a ==> a
aa ==> aa
aaa ==> ###
aaaaaaa ==> #######
aayyyycbbbee ==> aacee#######
xavvvarrrt ==> xaat######
xxxaaaaxxxaaa ==> #############
xxaavvvaarrrbbsssgggtt ==> xxaaaabbtt############
*/

The idea is to keep the current index for reading the next character and one for writing, as well as the number of consecutive repeated characters. If the following character is equal to the current, we just increase the counter. Otherwise we copy all characters below a count of 3, increasing the write index appropriately.

At the end of reading, anything from the current write index up to the end of the array is the number of repeated characters we have skipped. We just fill that with hashes now.

As we only store 3 values, memory consumption is O(1); we read each array cell twice, so O(n) time (the extra reads on writing could be eliminated by another variable); and each write index is accessed exactly once.

Upvotes: 1

גלעד ברקן
גלעד ברקן

Reputation: 23955

This seems to work with your examples, although it seems a little complicated to me :) I wonder if we could simplify it. The basic idea is to traverse from left to right, keeping a record of how many places in the current block of duplicates are still available to replace, while the right pointer looks for more blocks to shift over.

JavaScript code:

function f(str){
  str = str.split('')
  let r = 1
  let l = 0
  let to_fill = 0
  let count = 1
  let fill = function(){
    while (count > 0 && (to_fill > 0 || l < r)){
      str[l] = str[r - count]
      l++
      count--
      to_fill--
    }
  }
  for (; r<str.length; r++){
    if (str[r] == str[r-1]){
      count++
        
    } else if (count < 3){
      if (to_fill)
        fill()
      count = 1
      if (!to_fill)
        l = r

    } else if (!to_fill){
      to_fill = count
      count = 1
      
    } else {
      count = 1
    }
  }
 
  if (count < 3)
    fill()
  
  while (l < str.length)
    str[l++] = '#'

  return str.join('')
}

var str = "aayyyycbbbee"
console.log(str)
console.log(f(str)) // "aacee#######"

str = "xavvvarrrt"
console.log(str)
console.log(f(str)) // "xaat######"

str = "xxaavvvaarrrbbsssgggtt"
console.log(str)
console.log(f(str))

Upvotes: 2

Related Questions