Link: https://www.nowcoder.com/questionTerminal/504ad6420b314e5bb614e1684ad46d4d Source: NowCoder

A valid bracket matching sequence is defined as:

1. An empty string "" is a valid bracket sequence
2. If “X” and “Y” are valid sequences, then “XY” is also a valid bracket sequence
3. If “X” is a valid sequence, then “(X)” is also a valid bracket sequence
4. Every valid bracket sequence can be generated using the above rules For example, “”, “()”, “()()()”, “(()())”, “(((())))” are all valid. A sequence obtained by removing zero or more characters from a string S is called a subsequence of S. For example, the subsequences of “abcde” include “abe”, “”, “abcde”, etc. Define LCS(S,T) as the length of the longest common subsequence between string S and string T, which is the length of the longest sequence W that is both a subsequence of S and a subsequence of T. Xiaoyi gives you a valid bracket matching sequence s, and he hopes you can find a bracket sequence t with the following characteristics:
5. t is different from s but has the same length
6. t is also a valid bracket matching sequence
7. LCS(s, t) is the largest among all t that satisfy the above two conditions Since there may be multiple such t, Xiaoyi needs you to calculate how many such t exist.

As shown in the example: s = “(())()”, valid bracket matching sequences with the same length as s include: “()(())”, “((()))”, “()()()”, “(()())”, where LCS("(())()", “()(()))”) is 4, and the others are all 5, so the output is 3.

Input Description:

Output Description:

Output a positive integer, the number of t that satisfy the conditions.

Example 1

Input

(())()

Output

3

Analysis

The problem requires iterating through all bracket sequences of the same length and calculating the length of the longest common subsequence between each bracket sequence and the given string. Then, count how many times the maximum length occurs.

If we were to follow the problem description exactly, it would be impossible to solve. Just generating bracket sequences of up to 50 characters would likely exceed the time limit.

Since we’re searching for how many times the longest subsequence occurs, we can assume that the longest subsequence is the original string length - 1, and then find all bracket sequences that can be formed from this subsequence. If none exist, we try subsequences of length original length - 2, and so on, decreasing the subsequence length until we find a solution.

In fact, there always exists a subsequence of length original length - 1 that can form another valid bracket sequence different from the original. This is because any bracket sequence can be modified by moving just one bracket to form another different valid bracket sequence (think about why). If this is possible, then the longest common subsequence between the new string and the original string would be n-1, since you only moved one bracket to a new position. The order of all other brackets remains unchanged. So, each time we remove one bracket and insert it in a new position. We count how many valid bracket sequences can be formed this way, subtract the original string (i.e., subtract 1), and that’s the answer to the problem.

#include <vector>
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

bool isKuohao(const string & str)
{
    int count=0;
    for(auto c:str)
    {
        if(c == '(')
            count ++;
        if(c == ')')
            count --;
        if(count<0)
            return false;
    }
    return count == 0;
}

int main()
{
    int ret=0;
    string input;
    cin >> input;
    set<string> haveChose;
    set<string> haveBuild;
    /* Select any one bracket */
    for (int i = 0; i < input.size(); i++)
    {
        char q[] = {input[i], '\0'};
        /* Delete that bracket */
        string delete_char(input);
        delete_char.erase(delete_char.begin() + i);
        if (haveChose.count(delete_char))
            continue;
        else
            haveChose.insert(delete_char);
        /* Insert the original bracket into a new array */
        for (int j = 0; j < delete_char.size() + 1; j++)
        {
            string add_delete_char(delete_char);
            add_delete_char.insert(j, q);
            if (haveBuild.count(add_delete_char))
                continue;
            else
                haveBuild.insert(add_delete_char);
            if(isKuohao(add_delete_char)){
                ret ++;
            }
        }
    }
    cout << ret-1 << endl;
}