RNR's blog

How to solve this string edit problem
By RNR, history, 5 years ago, In English

How to solve a generalization of this problem?

Given a string, remove identical consecutive letters ( not only pair as mentioned in the above question).

For example, if you have

wwwhaat --> ht
whhhaah --> w
reallazy --> rezy
whaahhhh --> w

Can someone suggest me an algorithm? For finding the minimum string at the end of this deletion?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Use stack and go backwards. If next element is equal to top of stack, pop top element and continue with next, otherwise, add that element to top of the stack.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How does this work? When the input is "wwwhaat" I think whatever you suggest outputs "wht". Can you check this?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      Well yes, but then if you have this case when next character is equal to top of the stack, iterate until you have character that is not equal to top of the stack and then pop it.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        bawwaaab at what point do you pop a and w ?

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        But what if we have "whhhaah", I think then your solution will give "wh", while the correct answer is "w"?

        → Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

if we have baabba, what should be result? ba or a? That's the problem when you generalize this problem :) In both cases though, you should do a simulation with a linkedlist so erasing an element is constant time. If the answer is a, it can be done in O(N), as after each block deletion, you can check if previous character is equal to next, otherwise you have to do simulations from beginning until there is no deletion.

→ Reply