Longest Valid Parantheses Solution

cleaned-main.cpp

class Solution {
public:
    int longestValidParentheses(string s) {
        uint count = 0;

        char lp = '(';

        char emptyChar = '\0';

        char rp = ')';

        stack<tuple<char, uint>> sps;

        uint prevCompletedCount = 0;

        sps.push(make_tuple(emptyChar, 0));

        stack<tuple<uint, tuple<uint, uint>>> countSas;

        uint greatestCount = 0;

        uint size = s.size();

        for (uint i = 0; i < size; i++) {
            char thisChar = s.at(i);
            auto topItem = sps.top();

            char prev = get<0>(topItem);

            uint prevI = get<1>(topItem);



            if (prev == lp && thisChar == lp) { // ((
                sps.push(make_tuple(thisChar, i));
            }
            else if (prev == rp && thisChar == rp) { // ))
                sps.push(make_tuple(thisChar, i));
            }
            else if (thisChar == rp && prev == lp) { // ()
                sps.pop();

                bool stackIsEmpty = countSas.empty();

                if (stackIsEmpty) {
                    greatestCount = 2;
                    
                    countSas.push(make_tuple(2, make_tuple(prevI, i)));

                    continue;
                }

                auto neighbour = countSas.top();

                uint prevCount = get<0>(neighbour);

                auto neighbourIRange = get<1>(neighbour);

                uint neighbourI1 = get<0>(neighbourIRange);

                uint neighbourI2 = get<1>(neighbourIRange);

                uint newCount = prevCount + 2;

                auto newItemToPush = make_tuple(newCount, make_tuple(prevI, i));

                if (prevI < neighbourI1 && i > neighbourI2) {

                    countSas.pop();


                    if (countSas.empty() == false) {
                        auto newTop = countSas.top();

                        while (get<1>(get<1>(newTop)) + 1 == prevI) {

                            newCount = get<0>(newTop) + newCount;

                            uint y2 = get<1>(get<1>(newTop));

                            uint y1 = get<0>(get<1>(newTop));
                            
                            newItemToPush = make_tuple(newCount, make_tuple(y1 < i ? y1 : i, y2 < i ? i : y2 ));

                        
                            countSas.pop();

                            if (countSas.empty() == false) {
                                newTop = countSas.top();
                            }
                            else {
                                break;
                            }
                        }
                    }
                }
                else if (neighbourI2 + 1 == prevI) {
                    countSas.pop();

                    newItemToPush = make_tuple(newCount, make_tuple(neighbourI1, i));
                }
                else {
                    newItemToPush = make_tuple(2, make_tuple(prevI, i));
                    newCount = 2;
                }

                countSas.push(newItemToPush);

                if (greatestCount < newCount) greatestCount = newCount;

            }
            else if (thisChar == lp && prev == rp) { // )(

                sps.push(make_tuple(thisChar, i));
            }
            else if (prev == emptyChar && thisChar == rp) { // )
                if (i != 0) sps.push(make_tuple(thisChar, i));

            }
            else if (prev == emptyChar && thisChar == lp) { // (
                sps.push(make_tuple(thisChar, i));
            }

        }

        return greatestCount;
    }
};

pardon-my-uncleaned-code.cpp

class Solution {
public:
    int longestValidParentheses(string s) {
        uint count = 0;

        char lp = '(';

        char emptyChar = '\0';

        char rp = ')';

        stack<tuple<char, uint>> sps;

        uint prevCompletedCount = 0;

        sps.push(make_tuple(emptyChar, 0));

        stack<tuple<uint, tuple<uint, uint>>> countSas;

        uint greatestCount = 0;

        uint size = s.size();

        for (uint i = 0; i < size; i++) {
            char thisChar = s.at(i);
            auto topItem = sps.top();

            char prev = get<0>(topItem);

            uint prevI = get<1>(topItem);

            // uint startSubstr = get<1>(spsTop);

            printf("Prev: %c ; Curr: %c\n\n", prev, thisChar);


            printf("prevI: %i, %i --- i\n\n", prevI, i);

            if (prev == lp && thisChar == lp) { // ((
                printf("((\n");


                
                sps.push(make_tuple(thisChar, i));
            }
            else if (prev == rp && thisChar == rp) { // ))
                printf("))\n");

                sps.push(make_tuple(thisChar, i));
            }
            else if (thisChar == rp && prev == lp) { // ()
                printf("()\n");

                sps.pop();

                bool stackIsEmpty = countSas.empty();

                if (stackIsEmpty) {
                    greatestCount = 2;
                    
                    countSas.push(make_tuple(2, make_tuple(prevI, i)));

                    printf("\n-------\n\n");


                    continue;
                }

                auto neighbour = countSas.top();

                uint prevCount = get<0>(neighbour);

                auto neighbourIRange = get<1>(neighbour);

                uint neighbourI1 = get<0>(neighbourIRange);

                uint neighbourI2 = get<1>(neighbourIRange);

                uint newCount = prevCount + 2;

                printf("prevI: %i, neighbourI1: %i, neighbourI2: %i, i: %i\n\n\n", prevI, neighbourI1, neighbourI2, i);

                auto newItemToPush = make_tuple(newCount, make_tuple(prevI, i));

                if (prevI < neighbourI1 && i > neighbourI2) {
                    cout << "Merge something 1\n\n";


                    countSas.pop();


                    if (countSas.empty() == false) {
                        cout << "looping\n\n";


                        auto newTop = countSas.top();

                        printf("i1: %i, i2: %i, prevI: %i\n\n", get<0>(get<1>(newTop)), get<1>(get<1>(newTop)), prevI);



                        while (get<1>(get<1>(newTop)) + 1 == prevI) {

                            newCount = get<0>(newTop) + newCount;

                            uint y2 = get<1>(get<1>(newTop));

                            uint y1 = get<0>(get<1>(newTop));
                            
                            newItemToPush = make_tuple(newCount, make_tuple(y1 < i ? y1 : i, y2 < i ? i : y2 ));

                            cout << "A new match v2!!!";

                            countSas.pop();

                            if (countSas.empty() == false) {
                                newTop = countSas.top();
                            }
                            else {
                                break;
                            }
                        }
                    }
                }
                else if (neighbourI2 + 1 == prevI) {
                    cout << "Merge something 2\n\n";

                    countSas.pop();

                    newItemToPush = make_tuple(newCount, make_tuple(neighbourI1, i));
                }
                else {
                    newItemToPush = make_tuple(2, make_tuple(prevI, i));
                    newCount = 2;
                }

                countSas.push(newItemToPush);

                if (greatestCount < newCount) greatestCount = newCount;

            }
            else if (thisChar == lp && prev == rp) { // )(
                printf(")(\n");

                // sps.pop();

                sps.push(make_tuple(thisChar, i));
            }
            else if (prev == emptyChar && thisChar == rp) { // )
                printf(")\n");

                if (i != 0) sps.push(make_tuple(thisChar, i));

            }
            else if (prev == emptyChar && thisChar == lp) { // (
                printf("(\n");

                sps.push(make_tuple(thisChar, i));
            }

            printf("\n-------\n\n");
        }

        uint i = 0;

        while (countSas.empty() == false) {
            auto topC = countSas.top();

            printf("\n\n----\n\nIndex: %i, Count: %i, range: [%i, %i]\n\n", i, get<0>(topC), get<0>(get<1>(topC)), get<1>(get<1>(topC)));

            i++;

            countSas.pop();
        }

        

        return greatestCount;
    }
};