Bracket sequence

#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << #x << ": " << x << endl;
#define ll long long
#define ull unsigned long long
#define vi vector<int>


bool check_valid_pattern(const string &s) {
    int count = 0;
    for (char c : s) {
        if (c == '(') {
            count++;
        }

        else { // ')'
            if (count == 0) {
                return false;
            } else {
                count--;
            }
        }
    }

    return count == 0;
}


string longest_valid_pattern(string s) {
    int count = 0;

    string result = "";

    string current = "";
    for (char c : s) {

        current += c;

        if (c == '(') {
            count++;
        }

        else { // ')'
            if (count == 0) {
                current = "";
            } else {
                count--;
            }
        }

        if (current.size() > result.size() && count == 0) result = current;
    }

    current = s.substr(count,s.size()-count);
    
    if (check_valid_pattern(current) && current.size() > result.size()) result = current;

    return result;
}

string longestRegularSubstring(const string& s) {
    int n = s.size();
    vector<int> dp(n, 0); // dp[i] will store the length of the longest valid substring ending at index i
    int maxLength = 0;
    int endIndex = -1;

    for (int i = 1; i < n; ++i) {
        if (s[i] == ')') {
            int j = i - dp[i - 1] - 1; // index of the matching '(' for the current ')'
            if (j >= 0 && s[j] == '(') {
                dp[i] = dp[i - 1] + 2;
                if (j > 0) {
                    dp[i] += dp[j - 1];
                }
                if (dp[i] > maxLength) {
                    maxLength = dp[i];
                    endIndex = i;
                }
            }
        }
    }

    if (maxLength == 0) {
        return "-1";
    } else {
        return s.substr(endIndex - maxLength + 1, maxLength);
    }
}

int main() {
    string s;
    cin >> s;
    cout << longestRegularSubstring(s) << endl;
    return 0;
}













// string reverse_par(string &s) {
//     string r = "";
//     for (auto it = s.rbegin(); it != s.rend(); it++) {
//         if (*it == '(') r += ')';
//         else r += '(';
//     }
//     return r;
// }


// int main() {
//     string s;
//     cin >> s;

//     string r1 = longest_valid_pattern(s);
//     // string r2 = longest_valid_pattern(reverse_par(s));


//     if (r1.size() > 0) cout << r1 << endl;
//     // else if (r2.size() > 0) cout << reverse_par(r2) << endl;

//     else cout << -1 << endl;

//     return 0;
// }

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: ACCEPTED

Test 45

Verdict: ACCEPTED

Test 46

Verdict: ACCEPTED

Test 47

Verdict: ACCEPTED

Test 48

Verdict: ACCEPTED

Test 49

Verdict: ACCEPTED

Test 50

Verdict: ACCEPTED

Test 51

Verdict: ACCEPTED

Test 52

Verdict: ACCEPTED

Test 53

Verdict: ACCEPTED

Test 54

Verdict: ACCEPTED

Test 55

Verdict: ACCEPTED

Test 56

Verdict: ACCEPTED

Test 57

Verdict: ACCEPTED

Test 58

Verdict: ACCEPTED

Test 59

Verdict: ACCEPTED

Test 60

Verdict: ACCEPTED

Test 61

Verdict: ACCEPTED

Test 62

Verdict: ACCEPTED

Test 63

Verdict: ACCEPTED

Test 64

Verdict: ACCEPTED

Test 65

Verdict: ACCEPTED