解题思路

给定只含 (、)、* 的字符串，题意要求：在某个连续子串中，把所有 * 全部忽略（删除）后，剩下的括号序列必须是有效括号串。于是可将问题转化为：

1. 先把整串中过滤出所有括号，得到只含 (、) 的序列 par，并记录这些括号在原串中的位置数组 pos。

2. 在 par 上求“最长有效括号”（经典 LVP）——可用 O(n) DP：

   • 设 dp[i] 表示以 i 位置结尾的最长有效括号长度（单位：括号个数），若 par[i] == ')' 且与其匹配的左括号在 j = i - 1 - dp[i-1] 且 par[j] == '('，则 dp[i] = dp[i-1] + 2 (+ dp[j-1] 若 j-1 >= 0).

3. par 中任一有效段 [p..i] 在原串中对应的最小覆盖区间是 [pos[p], pos[i]]，而由于子串中 * 会被忽略，我们可以把这个区间向左右再扩展，把紧贴两端的连续 * 一并纳入，仍然满足题意。 为便于 O(1) 计算左右可扩展的星号数量，预处理：

   • preStar[k]：以 k 结束的连续 * 的长度（前缀方向）。
   • sufStar[k]：从 k 开始的连续 * 的长度（后缀方向）。
   • 对于括号在原串位置 x = pos[t]： 左端可扩展星数 leftRun[t] = (x>0 && s[x-1]=='*') ? preStar[x-1] : 0； 右端可扩展星数 rightRun[t] = (x+1<n && s[x+1]=='*') ? sufStar[x+1] : 0。 则有效段 [p..i] 对应的原串最长合法长度为 len = (pos[i] - pos[p] + 1) + leftRun[p] + rightRun[i]。

4. 还要考虑只由 * 组成的子串：忽略后为空串，仍然有效。因此答案还需与“最大连续 * 的长度”取最大。

整体为 O(n) 线性算法，适配大数据范围。

复杂度分析

• 时间复杂度：对每个测试用例，线性扫描与 DP 各一次，O(n)。
• 空间复杂度：若 m 为括号个数，辅助数组规模为 O(n) 与 O(m)，总体 O(n)。

代码实现

Python

# -*- coding: utf-8 -*-
import sys

def solve_case(s: str) -> int:
    n = len(s)
    if n == 0:
        return 0

    # 预处理：连续星号的前缀/后缀长度
    pre = [0] * n  # 以 i 结尾的连续 '*'
    suf = [0] * n  # 以 i 开始的连续 '*'
    max_star_run = 0

    for i in range(n):
        if s[i] == '*':
            pre[i] = (pre[i - 1] + 1) if i > 0 else 1
        else:
            pre[i] = 0
        if pre[i] > max_star_run:
            max_star_run = pre[i]

    for i in range(n - 1, -1, -1):
        if s[i] == '*':
            suf[i] = (suf[i + 1] + 1) if i + 1 < n else 1
        else:
            suf[i] = 0

    # 抽取括号与其原串位置
    pos = []
    par = []
    for i, ch in enumerate(s):
        if ch != '*':
            pos.append(i)
            par.append(ch)

    m = len(pos)
    if m == 0:
        # 全是星号，最大连续星号段即为答案
        return max_star_run

    # 计算每个括号位置两端可扩展的星号
    left_run = [0] * m
    right_run = [0] * m
    for t in range(m):
        x = pos[t]
        left_run[t] = pre[x - 1] if x > 0 else 0
        right_run[t] = suf[x + 1] if x + 1 < n else 0

    # 经典 LVP 的 DP，单位是括号个数
    dp = [0] * m
    ans = max_star_run  # 先考虑纯星号段

    for i in range(m):
        if par[i] == ')':
            prev = dp[i - 1] if i > 0 else 0
            j = i - 1 - prev
            if j >= 0 and par[j] == '(':
                dp[i] = prev + 2
                if j - 1 >= 0:
                    dp[i] += dp[j - 1]
                p = i - dp[i] + 1  # 有效段在 par 上的起点
                cur_len = (pos[i] - pos[p] + 1) + left_run[p] + right_run[i]  # 扩展两端星号后的原串长度
                if cur_len > ans:
                    ans = cur_len
        # 若 par[i] == '(' 则 dp[i] = 0（默认）

    return ans

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    T = int(next(it))
    out = []
    for _ in range(T):
        n = int(next(it))  # 题目保证合法
        s = next(it).decode()
        out.append(str(solve_case(s)))
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

Java

// ACM 风格，类名为 Main
// 思路：在只含括号的序列上做 LVP DP，再在原串中用两端星号扩展长度；并与纯星号最大段取最大
import java.io.*;
import java.util.*;

public class Main {
    // 读取输入的简易快读
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;

        FastScanner(InputStream is) { in = is; }

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }

        String next() throws IOException {
            StringBuilder sb = new StringBuilder();
            int c;
            while ((c = read()) <= 32) {
                if (c == -1) return null;
            }
            while (c > 32) {
                sb.append((char) c);
                c = read();
            }
            return sb.toString();
        }

        int nextInt() throws IOException {
            int c, sgn = 1, x = 0;
            do { c = read(); } while (c <= 32);
            if (c == '-') { sgn = -1; c = read(); }
            while (c > 32) {
                x = x * 10 + (c - '0');
                c = read();
            }
            return x * sgn;
        }
    }

    static int solveCase(String s) {
        int n = s.length();
        if (n == 0) return 0;

        int[] pre = new int[n]; // 以 i 结尾的连续 '*'
        int[] suf = new int[n]; // 以 i 开始的连续 '*'
        int maxStarRun = 0;

        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '*') {
                pre[i] = (i > 0 ? pre[i - 1] + 1 : 1);
            } else pre[i] = 0;
            if (pre[i] > maxStarRun) maxStarRun = pre[i];
        }
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == '*') {
                suf[i] = (i + 1 < n ? suf[i + 1] + 1 : 1);
            } else suf[i] = 0;
        }

        // 收集括号及其原串位置
        ArrayList<Integer> pos = new ArrayList<>();
        ArrayList<Character> par = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (ch != '*') {
                pos.add(i);
                par.add(ch);
            }
        }
        int m = pos.size();
        if (m == 0) return maxStarRun; // 纯星号

        int[] leftRun = new int[m];
        int[] rightRun = new int[m];
        for (int t = 0; t < m; t++) {
            int x = pos.get(t);
            leftRun[t] = (x > 0 ? pre[x - 1] : 0);
            rightRun[t] = (x + 1 < n ? suf[x + 1] : 0);
        }

        int[] dp = new int[m];
        int ans = maxStarRun;

        for (int i = 0; i < m; i++) {
            if (par.get(i) == ')') {
                int prev = (i > 0 ? dp[i - 1] : 0);
                int j = i - 1 - prev;
                if (j >= 0 && par.get(j) == '(') {
                    dp[i] = prev + 2;
                    if (j - 1 >= 0) dp[i] += dp[j - 1];
                    int p = i - dp[i] + 1;
                    int cur = (pos.get(i) - pos.get(p) + 1) + leftRun[p] + rightRun[i];
                    if (cur > ans) ans = cur;
                }
            } // 若为 '('，dp[i] 保持 0
        }
        return ans;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int T = Integer.parseInt(fs.next());
        StringBuilder out = new StringBuilder();
        for (int tc = 0; tc < T; tc++) {
            int n = fs.nextInt(); // 题目保证合法
            String s = fs.next();
            out.append(solveCase(s)).append('\n');
        }
        System.out.print(out.toString());
    }
}

C++

// 思路：在过滤后的括号串上做最长有效括号 DP；答案为该有效段在原串的覆盖长度再加两端可扩展的连续星号；与纯星号最大段取最大
#include <bits/stdc++.h>
using namespace std;

static inline int solve_case(const string &s) {
    int n = (int)s.size();
    if (n == 0) return 0;

    vector<int> pre(n, 0), suf(n, 0);
    int maxStarRun = 0;

    // 以 i 结尾的连续 '*'
    for (int i = 0; i < n; ++i) {
        if (s[i] == '*') pre[i] = (i > 0 ? pre[i - 1] + 1 : 1);
        else pre[i] = 0;
        if (pre[i] > maxStarRun) maxStarRun = pre[i];
    }
    // 以 i 开始的连续 '*'
    for (int i = n - 1; i >= 0; --i) {
        if (s[i] == '*') suf[i] = (i + 1 < n ? suf[i + 1] + 1 : 1);
        else suf[i] = 0;
    }

    // 收集括号及原位置
    vector<int> pos;
    vector<char> par;
    pos.reserve(n);
    par.reserve(n);
    for (int i = 0; i < n; ++i) {
        if (s[i] != '*') { pos.push_back(i); par.push_back(s[i]); }
    }

    int m = (int)pos.size();
    if (m == 0) return maxStarRun; // 全是星号

    vector<int> leftRun(m, 0), rightRun(m, 0);
    for (int t = 0; t < m; ++t) {
        int x = pos[t];
        leftRun[t] = (x > 0 ? pre[x - 1] : 0);
        rightRun[t] = (x + 1 < n ? suf[x + 1] : 0);
    }

    vector<int> dp(m, 0);
    int ans = maxStarRun;

    for (int i = 0; i < m; ++i) {
        if (par[i] == ')') {
            int prev = (i > 0 ? dp[i - 1] : 0);
            int j = i - 1 - prev;
            if (j >= 0 && par[j] == '(') {
                dp[i] = prev + 2;
                if (j - 1 >= 0) dp[i] += dp[j - 1];
                int p = i - dp[i] + 1;
                int cur = (pos[i] - pos[p] + 1) + leftRun[p] + rightRun[i];
                ans = max(ans, cur);
            }
        }
        // 若为 '('，dp[i] = 0
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; 
    if (!(cin >> T)) return 0;
    while (T--) {
        int n; string s;
        cin >> n >> s; // 输入保证合法
        cout << solve_case(s) << "\n";
    }
    return 0;
}

题目内容

多多最近在处理一个字符串问题，该字符串由 '$($'、'$)$' 和 '$*$' 组成，多多希望找到最长的连续子串，使得当忽略所有 '$*$' 后，该子串是一个有效的括号子串。

有效括号子串需满足：

1. 括号成对闭合：每个 '$($' 都有一个对应的 '$)$'
2. 正确嵌套顺序：右括号不能出现在对应的左括号之前

输入描述

第一行输入为一个整数 $T$, 表示测试用例的组数 $(1 <= T <= 100)$

接下来 $T$ 组数据，每组测试用例包含两行:

第一行输入为一个整数 $N$ , 表示字符串的总长度 $(1 <= N <= 500,000)$

第二行输入为一个长度为 $N$ 字符串，字符串由 $($ 和 $)$ 以及 $*$ 组成

输出描述

输出包含 $T$ 行

每一输出为一个整数，满足要求的最长的连续子串的长度

补充说明

空字符串是有效括号子串

样例1

输入

3
8
*(*(**))
4
(()*
8
*(()(*)*

输出

8
3
6

样例2

输入

2
4
****
4
)))(

输出

4
0