1209. Remove All Adjacent Duplicates in String II ----Medium

You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together.

We repeatedly make k duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique.

 

Example 1:

Input: s = "abcd", k = 2
Output: "abcd"
Explanation: There's nothing to delete.

Example 2:

Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation: 
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"

Example 3:

Input: s = "pbbcggttciiippooaais", k = 2
Output: "ps"

 

Constraints:

• 1 <= s.length <= 105
• 2 <= k <= 104
• s only contains lowercase English letters.

 

A:

就是自己弄了个linkded list， 然后一个个加上然后再删除的

（好处是方便最好一个增加或者删除） --------只是beat了 38%

class Solution {

public:

string removeDuplicates(string s, int k) {

int n = s.size();

Node header('@');

Node * tail = &header;

for(char ch : s){

if(ch == tail->ch){

tail->count ++;

if(tail->count == k){

tail = tail->pre;

delete tail->next;

tail->next = nullptr;

}

}else{

Node* node = new Node(ch);

node->pre = tail;

tail->next = node;

tail = tail->next;

}

}

string res;

auto runner = header.next;

while(runner){

string ss(runner->count, runner->ch);

header.next = runner->next;

delete runner;

runner = header.next;

res += ss;

}

return res;

}

private:

struct Node{

char ch;

int count;

Node* pre;

Node* next;

Node(char ch2) : ch(ch2), count(1), pre(nullptr), next(nullptr) {}

};

};

-----------------第二遍----------- 只是用了个vector， 因为根据上面的linkedlist， 我们也只是需要处理最后一个位置就行---------  但也只是beat了66%----

class Solution {

public:

string removeDuplicates(string s, int k) {

vector<pair<char, int>> V;

for(char ch : s){

if(V.empty() || ch != V.back().first){

V.emplace_back(ch,1);

}else{

V.back().second ++;

if(V.back().second == k){

V.pop_back();

}

}

}

string res;

for(auto it : V){

res += string(it.second, it.first);

}

return res;

}

};

----------再仔细看， 其实就只是用stack----------

然而改了后，并没有变快。

Learned: 

不能在循环里用

for(char ch : s){

if(ch == tail->ch){

tail->count ++;

if(tail->count == k){

tail = tail->pre;

tail->next = nullptr;

}

}else{

Node newTail(ch);

tail->next = &newTail;

tail = tail->next;

}

}

而需要用new

You're getting a "stack-use-after-scope" error because of this line in your code:

Node newTail(ch);
tail->next = &newTail;

This creates a stack-allocated Node (newTail), then stores a pointer to it in the linked list. But after that iteration of the loop ends, newTail goes out of scope and is destroyed, leaving a dangling pointer.