# PROBLEM LINK:

Authors: akshay_2512, divyesh_11
Tester & Editorialist: iceknight1093

TBD

# PREREQUISITES:

Dynamic programming

# PROBLEM:

You’re given a string S consisting of lowercase Latin characters.
Find a bracket sequence T of the same length as S such that:

• T is a regular bracket sequence
• If S_i = S_{i+1}, then T_i = T_{i+1}

# EXPLANATION:

The condition S_i = S_{i+1} \implies T_i = T_{i+1} means that each contiguous block of equal characters in S must correspond to a contiguous block of either ( or ), of the same length, in T.

So, let’s find all the maximal contiguous blocks of equal characters in S.
Suppose there are k such blocks, and their lengths are L_1, L_2, \ldots, L_k in order.
For example, if S = \texttt{aabacccbbddd} then L = [2, 1, 1, 3, 2, 3].

Now, for each of these blocks, we need to decide whether it corresponds to ( or ).
There are 2^k possibilities, and since k can be as large as N, checking each one is out of the question.

Instead, note that T is a regular bracket sequence iff:

• Each prefix of T has a non-negative balance.
• T as a whole has balance 0.

Here, the balance of a bracket sequence equals the number of opening parentheses it contains, minus the number of its closing parentheses.
For example, the balance of \texttt{()} and \texttt{)(} are both 0, while \texttt{)(()(} has balance 3-2=1.

This allows us to only have to deal with prefixes; in particular, we only really care about the balance of each prefix.
This reduction lets us use dynamic programming.

Let \text{dp}[i][j] be a boolean value: True if there is a way to assign ( and ) to the first i blocks such that resulting balance is exactly j; and false otherwise.
Note that we only care about j \geq 0, since the balance cannot be allowed to go negative.

With this definition, transitions are in fact quite straightforward.
There are two choices for the i-th block: ( or ). Trying each one,

• If the i-th block is turned into (, it will increase the balance by exactly A_i.
So, the part before it must have a balance of j - A_i, and we can check whether this is possible by looking at \text{dp}[i][j - A_i]
• Similarly, if the i-th block is turned into ), we need to look at \text{dp}[i-1][j + A_i].
• So, we have \text{dp}[i][j] = \text{dp}[i-1][j - A_i] \mid \text{dp}[i-1][j + A_i], where \mid denotes the bitwise OR operator.

Of course, the final answer is Yes if \text{dp}[k][0] is True, and No otherwise; because the overall balance after all k blocks are assigned, should be 0.

If a solution exists, reconstructing it is not hard: move from the last block to the first, and each time the stored dp values will tell you which transition you took; and hence which type of bracket to assign to the current block.

There are upto \mathcal{O}(N^2) states and \mathcal{O}(1) transitions for each, for \mathcal{O}(N^2) time overall.

# TIME COMPLEXITY

\mathcal{O}(N^2) per testcase.

# CODE:

Author's code (C++)
// author : divyesh_11
#include<bits/stdc++.h>
using namespace std;

#define ll long long

vector<vector<int>> dp;
vector<ll> pre;

int helper(ll i, ll val, ll n, ll size, vector<ll> &a)
{
if (i >= n)
{
return val == 0;
}
if (dp[i][val] != -1)
{
return dp[i][val];
}
int ans1 = 0;
int ans2 = 0;
if (val >= a[i])
{
ans1 = helper(i + 1, val - a[i], n, size, a);
}
ll can = (size - pre[i] - val) / 2;
if (can >= a[i])
{
ans2 = helper(i + 1, val + a[i], n, size, a);
}
return dp[i][val] = (ans1 || ans2);
}

void solve()
{
ll n;
cin >> n;

string s;
cin >> s;

if (n & 1)
{
cout << "NO" << endl;
return;
}

vector<ll> a;
ll count = 1;
char c = s[0];
for (int i = 1; i < n; i++)
{
if (s[i] == c)
{
count++;
}
else
{
a.push_back(count);
count = 1;
c = s[i];
}
}
a.push_back(count);
ll size = a.size();
pre.clear();
pre.resize(size + 1, 0);
dp.clear();
dp.resize(size + 1, vector<int>(n + 1, -1));
pre[1] = a[0];
for (int i = 2; i <= size; i++)
{
pre[i] = pre[i - 1] + a[i - 1];
}
if (helper(0, 0, size, n, a))
{
cout << "yes" << endl;
ll curr = 0;
ll i = 0;
string ans;
while (i < size - 1)
{
if (dp[i + 1][curr + a[i]] == 1)
{
ll count = a[i];
while (count--)
{
ans.push_back('(');
}
curr += a[i];
}
else
{
ll count = a[i];
while (count--)
{
ans.push_back(')');
}
curr -= a[i];
}
i++;
}
while (a[i]--)
{
ans.push_back(')');
}
cout << ans << endl;
}
else
{
cout << "no" << endl;
}
}

int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int t = 1;
cin >> t;

for (int i = 1; i <= t; i++)
{
solve();
}

return 0;
}

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
s = input()
lens = []
cur, L = 0, 0
for i in range(n):
if s[i] == s[L]: cur += 1
else:
lens.append(cur)
cur = 1
L = i
lens.append(cur)

dp = [ [False for _ in range(n+1)] for _ in lens ]
dp[0][lens[0]] = True
for i in range(1, len(lens)):
x = lens[i]
for j in range(n+1):
if j >= x: dp[i][j] |= dp[i-1][j-x]
if j+x <= n: dp[i][j] |= dp[i-1][j+x]
if dp[-1][0] == 0: print('No')
else:
print('Yes')
ans = ''
cur = 0
for i in reversed(range(len(lens))):
x = lens[i]
if cur >= x and dp[i-1][cur-x] == True:
cur -= x
ans += '('*x
else:
cur += x
ans += ')'*x
print(ans[::-1])

2 Likes

Can anyone please help me in figuring out, on which test case my code is failing. It would be great help, Thanks in advance!

#include <bits/stdc++.h>
using namespace std;

#define ull unsigned long long
#define int long long

string ans;
int n;
string s,t;

int dp[2001][1002];

bool solve(int i,int count){
if(count < 0 || count > (n+1)/2) return false;
if(i == n){
if(count == 0){
ans = t;
return true;
}
return false;
}
if(dp[i][count] != -1) return dp[i][count];
if(i == 0){
t[i] = '(';
return solve(i+1,count+1);
}
if(s[i] == s[i-1]){
t[i] = t[i-1];
int del = t[i]==')'?-1:1;
return dp[i][count] = solve(i+1,count+del);
}
bool ok = false;
t[i] = '(';
ok = ok|| solve(i+1,count+1);
t[i] = ')';
return dp[i][count] =  ok || solve (i+1,count-1);
}

void solve(){
ans = "";
cin>>n;
cin>>s;
t = s;
memset(dp,-1,sizeof(dp));
if(n%2 == 1){
cout<<"NO\n";
return;
}
if(solve(0,0)){
cout<<"YES\n";
cout<<ans<<"\n";
}
else cout<<"NO\n";
}

int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);

int t;
cin>>t;
while(t--){;
solve();
}
return 0;
}