#include <bits/stdc++.h>

using namespace std;

//***********************************************************************
// HackerRank Prepare > Algorithms > Strings: Two Characters
//***********************************************************************

// Given a string, remove characters until the string is made up of
// any two alternating characters. When you choose a character to
// remove, all instances of that character must be removed. Determine
// the longest string possible that contains just two alternating
// letters.

static constexpr int DEBUG = 1;

int alternate(string s) {
    int longestString = 0;
    cout << "string: " << s << endl;
    
    // get unique characters
    set<char> chars;
    for (auto i: s) chars.insert(i);
    vector<char> charsV;
    for (auto i: chars) charsV.push_back(i);
                            
    cout << "size: " << chars.size() << " unique chars: ";
    for (auto j: chars) {cout << j << " ";} cout << endl;
    
    auto isAlternating = [](const string& twoChars)
    {
        if (twoChars.size() < 2 || twoChars.at(0) == twoChars.at(1))
        {
            cout << "  not alternating" << endl;
            return false;
        }

        for (size_t i = 2 ; i < twoChars.size(); i++)
        {
            if (twoChars.at(i%2) != twoChars.at(i))
            {
                cout << "  not alternating" << endl;
                return false;
            }
        }
        
        cout << "  isAlternating: " << twoChars.size() << endl;
        return true;
    };

    // n choose 2 =  n * (n - 1) / 2
    size_t numCombinations = 0;    
    for (size_t i = 0; i < chars.size() - 1; i++)
    {
        for (size_t j = 1; j < chars.size(); j++)
        {
            if (j <= i)
                continue;
            
            string twoChars;
            for (auto c: s)
            {
                 if (c == charsV.at(i) || c == charsV.at(j))
                     twoChars.push_back(c);
            }
            
            cout << "[" << i << "," << j << "] [" << charsV.at(i) << "," << charsV.at(j) << "] " << twoChars << endl;

            if (DEBUG)
            {
                if (isAlternating(twoChars))
                    longestString = max(longestString, (int)twoChars.size());
            }
            else
            {                
                if (twoChars.size() < 2 || twoChars.at(0) == twoChars.at(1))
                    goto NOT_ALTERNATING;
                
                for (size_t i = 2; i < twoChars.size(); i++)
                    if (twoChars.at(i%2) != twoChars.at(i))
                        goto NOT_ALTERNATING;

                longestString = max(longestString, (int)twoChars.size());
            }
            
        NOT_ALTERNATING:
            
            numCombinations++;            
        }
    }
    cout << "numCombinations: " << numCombinations << endl;
    return longestString;
}


int main()
{
    vector<tuple<string,int>> testCases = {
        {"beabeefeab", 5},
        {"asdcbsdcagfsdbgdfanfghbsfdab", 8},
        {"txnbvnzdvasknhlmcpkbxdvofimsvqbvkswlkrchohwuplfujvlwpxtlcixpajjpaskrnjneelqdbxtiyeianqjqaikbukpicrwpnjvfpzolcredzmfaznnzd", 6},
        {"yz", 2},
    };

    for (auto test: testCases)
    {
        int longestStringLen = alternate(get<0>(test));
        cout << "LongestStringLen: " << longestStringLen << endl;
        cout << "expected: " << get<1>(test) << endl;
        cout << "-----------------------\n";
    }
    return 0;
}