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?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 143 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 135 |
| 8 | maroonrk | 133 |
| 9 | BledDest | 132 |
| 10 | qwexd | 129 |
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.
How does this work? When the input is "wwwhaat" I think whatever you suggest outputs "wht". Can you check this?
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.
bawwaaabat what point do you popaandw?But what if we have "whhhaah", I think then your solution will give "wh", while the correct answer is "w"?
You're right never thought about this, sorry
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.