Submission #8461764

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)
#define mp make_pair

int32 n;
string s;

int32 bfs(int32 i, deque<int32> que){
    if(i == n){
        return que.size();
    }
    if(que.empty()){
        que.push_back(s[i]);
        return bfs(i+1,que);
    }else if(s[i] == que.front()){
        que.pop_front();
        return bfs(i+1, que);
    }else if(s[i] == que.back()){
        que.pop_back();
        return bfs(i+1, que);
    }else{
        que.push_front(s[i]);
        int32 retval = bfs(i+1, que);
        que.pop_front();
        que.push_back(s[i]);
        retval = min(retval, bfs(i+1, que));
        return retval;
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    cin >> s;
    cout << bfs(0, deque<int32>()) << endl;
    return 0;
}

Submission Info

Judge Result