Mini Candy Crush

2 secs 1024 MB

この問題は、C++ でいうところの stack というデータ構造を用いることで解くことができます。
文字列を順番に stack へ入れていきながら、最後に入れた要素と同じだった場合に stack の最後に入れた要素を削除すればよいです。
計算量は $O(N)$ で、この問題を十分高速に解くことができました。

実装例(C++)

#include <bits/stdc++.h>

using namespace std;

int main(){
  string s;
  cin >> s;
  int n = s.size();
  stack<char> q;
  for(int i = 0; i < n; i++){
    if(q.size() && q.top() == s[i]){
      q.pop();
    }else{
      q.push(s[i]);
    }
  }
  string ans = "";
  while(q.size()){
    ans += q.top(); q.pop();
  }
  reverse(ans.begin(), ans.end());
  cout << ans << endl;
}