21 Days Training // Day 19

T2. necklace

My idea : enum.

Enumerate all possible cutting plans and check if it is valid.

A wrong way to check :

First, we need a stack.
Then, we access the all characters of S.

If the stack is empty or the top of the stack is different from the current character, push the character into the stack.
Otherwise, pop the first character in the stack.

Notice that is the string is symmetric, no matter where we start read the string, after a cycle, the stack must be empty.

So we can use this to check if a string is valid.

Code :

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

int main() {
    string S;cin >> S;
    int L=S.length();
    int ans=0;
    for (int cl=0;cl<L;cl++) {
        for (int cr=0;cr<L;cr++) {

            stack<char> match;
            string Sr;
            for (int i=0;i<L;i++) {
                if (cl<=i&&i<=cr) continue;
                Sr += S[i];
            }
            int Lr=L-(cr-cl+1);
            if (!(Lr&1)) {
                // Condition 1 : axis through 0 point
                for (int i=0;i<Lr;i++) {
                    if (match.empty()||match.top()!=Sr[i]) match.push(Sr[i]);
                    else match.pop();
                }
                if (match.empty()) {
                    ans = max(ans, Lr);
                    break;
                }
                while (!match.empty()) match.pop();
                //Condition 2 : axis through 2 points
                for (int i=0;i<(Lr>>1);i++) {
                    for (int j=0;j<Lr;j++) {
                        if (j==i||j==(i+(Lr>>1))) continue;
                        if (match.empty()||match.top()!=Sr[j]) match.push(Sr[j]);
                        else match.pop();
                    }
                }
                if (match.empty()) {
                    ans = max(ans, Lr);
                    break;
                }
                while (!match.empty()) match.pop();
            }
            else {
                //Condition 3 : axis through 1 point
                for (int i=0;i<Lr;i++) {
                    for (int j=0;j<Lr;j++) {
                        if (j==i) continue;
                        if (match.empty()||match.top()!=Sr[j]) match.push(Sr[j]);
                        else match.pop();
                    }
                }
                if (match.empty()) {
                    ans = max(ans, Lr);
                    break;
                }
                while (!match.empty()) match.pop();
            }
        }
    }
    cout << ans;
    return 0;
}

However, complexity : O(n^4)

Constraints :

Expected : 0/0

Solution