---
title: "最长合法括号子串"
created: 2025-11-28
tags:
  - 算法
---

# 最长合法括号子串

## 题目 [最长合法括号子串](https://www.acwing.com/problem/content/4201/)

![[image-0d7480ad.png]]

## 思路分析

上题的简化

思路见 [[括号画家|括号画家]]

多了一个计数 如果最长为6 然后有两条是6的 要把这个2记录下来

那就用一个temp把每轮的值存一下

与之前保存的最大答案比一下

如果更大 就更新

如过不是一开始的情况（0）且temp与最大答案相同

就cnt++

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

typedef pair<char,int> PCI;

string s;

int main()

{

    cin>>s;

    stack<PCI> stk;

    int idx=0;

    int ans=0,cnt=1;

    stk.push({'0',0});

    for(auto c:s){

        ++idx;

        if(stk.size() && (stk.top().first=='(' && c==')'))

            stk.pop();

        else

            stk.push({c,idx});

        int temp=idx-stk.top().second;

        if(temp>ans)

            ans=temp,cnt=1;

        else if(temp>0 && temp==ans)

            cnt++;

    }

    cout<<ans<<" "<<cnt<<endl;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[插松枝|插松枝]] 🏠 [[00-刷题理模型]] ➡️ [[栈的压入、弹出序列|栈的压入、弹出序列]]