Codechef - PETERSEN

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <string.h>

#define PI pair<int,int>
#define MP(a,b) make_pair(a,b)

#define MOD 1000000007
#define long long ll

using namespace std;

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        string s;
        cin >> s;
        int n = s.length();
        int a[n+1];
        for(int i=0; i<n; i++) a[i+1] = s[i] - 'A';
        int dp1[n+1], dp2[n+1];     // store prev (1-outer, 2-inner)

// dp1[i] = 1 means from (i-1)th to ith character, transition from outer to outer node is made
// dp1[i] = 2 means from (i-1)th to ith character, transition from inner to outer node is made
// dp2[i] = 1 means from (i-1)th to ith character, transition from outer to inner node is made
// dp2[i] = 2 means from (i-1)th to ith character, transition from inner to inner node is made

        dp1[1] = 1;
        dp2[1] = 1;
        for(int i=2; i<=n; i++)
        {
            if(a[i] == a[i-1])
            {
                if(dp2[i-1] != -1) dp1[i] = 2;      // outer to inner
                else dp1[i] = -1;
                if(dp1[i-1] != -1) dp2[i] = 1;      // inner to outer
                else dp2[i] = -1;
            }
            else
            {
                // adj
                if(a[i] == (a[i-1]+1)%5 || a[i-1] == (a[i]+1)%5)
                {
                    if(dp1[i-1] != -1) dp1[i] = 1;
                }
                else dp1[i] = -1;
                if(a[i] == (a[i-1]+2)%5 || a[i-1] == (a[i]+2)%5)
                {
                    if(dp2[i-1] != -1) dp2[i] = 2;
                }
                else dp2[i] = -1;
            }
        }

        if(dp1[n]==-1 && dp2[n]==-1)
        {
            cout << -1 << endl;
            return 0;
        }
        //~ for(int i=1; i<=n; i++) cout << dp1[i] << " "; cout << endl;
        //~ for(int i=1; i<=n; i++) cout << dp2[i] << " "; cout << endl;

        vector<int> p1;
        vector<int> p2;
        int nn = 1;
        for(int i=n; i>=1; i--)
        {
            if(nn==1 && dp1[i] != -1)
            {
                p1.push_back(a[i]);     // outer node
                nn = dp1[i];
            }
            else if(nn==2 && dp2[i] != -1)
            {
                p1.push_back(a[i]+5);   // inner node
                nn = dp2[i];
            }
        }

        nn = 2;
        for(int i=n; i>=1; i--)
        {
            if(nn==1 && dp1[i] != -1)
            {
                p2.push_back(a[i]);     // outer node
                nn = dp1[i];
            }
            else if(nn==2 && dp2[i] != -1)
            {
                p2.push_back(a[i]+5);   // inner node
                nn = dp2[i];
            }
        }

        reverse(p1.begin(), p1.end());
        reverse(p2.begin(), p2.end());
        int s1 = p1.size();
        int s2 = p2.size();
        if(s2 < s1 || s2==s1 && p1[0] < p2[0])
        {
            if(s1==n) for(int i=0; i<s1; i++) cout << p1[i];
            else cout << -1;
        }
        else if(s1 < s2 || s1==s2 && p2[0] < p1[0])
        {
            if(s2==n) for(int i=0; i<s2; i++) cout << p2[i];
            else cout << -1;
        }
        cout << endl;
    }
    return 0;
}