A bracket sequence is considered to be a valid bracket expression if any of the following conditions is true:
- it is empty;
- it has the form "(U)" where U is a valid bracket sequence;
- it has the form "VW" where V and W are valid bracket sequences.
For example, the sequence "(())()" is a valid bracket expression, but "((())(()" is not.
You are given a sequence of brackets S and you are allowed to rotate some of them. Bracket rotation means picking a single bracket and changing it into its opposite form (i.e. an opening bracket can be changed into a closing bracket and vice versa). The goal is to find the longest slice (contiguous substring) of S that forms a valid bracket sequence using at most K bracket rotations.
Write a function:
def solution(S, K)
that, given a string S consisting of N brackets and an integer K, returns the length of the maximum slice of S that can be transformed into a valid bracket sequence by performing at most K bracket rotations.
For example, given S = ")()()(" and K = 3, you can rotate the first and last brackets to get "(()())", which is a valid bracket sequence, so the function should return 6 (notice that you need to perform only two rotations in this instance, though).
Given S = ")))(((" and K = 2, you can rotate the second and fifth brackets to get ")()()(", which has a substring "()()" that is a valid bracket sequence, so the function should return 4.
Given S = ")))(((" and K = 0, you can't rotate any brackets, and since there is no valid bracket sequence with a positive length in string S, the function should return 0.
Write an efficient algorithm for the following assumptions:
- string S contains only brackets: '(' or ')';
- N is an integer within the range [1..30,000];
- K is an integer within the range [0..N].
def sol(S, K):
flips = K
o_stack = []
c_stack = []
result = 0
grr = False
for i, x in enumerate(S):
if x == '(':
o_stack.append(i)
elif o_stack:
o_stack.pop()
grr = True
else:
c_stack.append(i)
if 2 * flips < len(o_stack):
s = o_stack[-2 * flips - 1] + 1
elif not c_stack:
s = o_stack[0] + 1 if len(o_stack) & 1 else 0
else:
if len(o_stack) & 1:
rem_flips = flips - len(o_stack) / 2 - 2
c_len = len(c_stack) - 1
else:
c_len = len(c_stack)
rem_flips = flips - len(o_stack) / 2
if rem_flips == -1:
s = o_stack[0] + 1
elif 2 * rem_flips < c_len:
s = c_stack[c_len - 2 * rem_flips - 1] + 1
else:
if grr and (c_len & 1):
s = (0 if c_len - 2 * rem_flips < 2 else c_stack[c_len - 2 * rem_flips - 2] + 1) + 1
else:
s = (c_stack[0] + 1) if c_len & 1 else 0
result = max(result, i - s + 1)
return result
Traceback (most recent call last): File "user.py", line 107, in <module> main() File "user.py", line 84, in main result = sol.solution ( S, K ) AttributeError: 'module' object has no attribute 'solution'
Traceback (most recent call last): File "user.py", line 107, in <module> main() File "user.py", line 84, in main result = sol.solution ( S, K ) AttributeError: 'module' object has no attribute 'solution'
Traceback (most recent call last): File "user.py", line 107, in <module> main() File "user.py", line 84, in main result = sol.solution ( S, K ) AttributeError: 'module' object has no attribute 'solution'
def solution(S, K):
flips = K
o_stack = []
c_stack = []
result = 0
grr = False
for i, x in enumerate(S):
if x == '(':
o_stack.append(i)
elif o_stack:
o_stack.pop()
grr = True
else:
c_stack.append(i)
if 2 * flips < len(o_stack):
s = o_stack[-2 * flips - 1] + 1
elif not c_stack:
s = o_stack[0] + 1 if len(o_stack) & 1 else 0
else:
if len(o_stack) & 1:
rem_flips = flips - len(o_stack) / 2 - 2
c_len = len(c_stack) - 1
else:
c_len = len(c_stack)
rem_flips = flips - len(o_stack) / 2
if rem_flips == -1:
s = o_stack[0] + 1
elif 2 * rem_flips < c_len:
s = c_stack[c_len - 2 * rem_flips - 1] + 1
else:
if grr and (c_len & 1):
s = (0 if c_len - 2 * rem_flips < 2 else c_stack[c_len - 2 * rem_flips - 2] + 1) + 1
else:
s = (c_stack[0] + 1) if c_len & 1 else 0
result = max(result, i - s + 1)
return result
def solution(S, K):
flips = K
o_stack = []
c_stack = []
result = 0
grr = False
for i, x in enumerate(S):
if x == '(':
o_stack.append(i)
elif o_stack:
o_stack.pop()
grr = True
else:
c_stack.append(i)
if 2 * flips < len(o_stack):
s = o_stack[-2 * flips - 1] + 1
elif not c_stack:
s = o_stack[0] + 1 if len(o_stack) & 1 else 0
else:
if len(o_stack) & 1:
rem_flips = flips - len(o_stack) / 2 - 2
c_len = len(c_stack) - 1
else:
c_len = len(c_stack)
rem_flips = flips - len(o_stack) / 2
if rem_flips == -1:
s = o_stack[0] + 1
elif 2 * rem_flips < c_len:
s = c_stack[c_len - 2 * rem_flips - 1] + 1
else:
if grr and (c_len & 1):
s = (0 if c_len - 2 * rem_flips < 2 else c_stack[c_len - 2 * rem_flips - 2] + 1) + 1
else:
s = (c_stack[0] + 1) if c_len & 1 else 0
result = max(result, i - s + 1)
return result
def solution(S, K):
flips = K
o_stack = []
c_stack = []
result = 0
grr = False
for i, x in enumerate(S):
if x == '(':
o_stack.append(i)
elif o_stack:
o_stack.pop()
grr = True
else:
c_stack.append(i)
if 2 * flips < len(o_stack):
s = o_stack[-2 * flips - 1] + 1
elif not c_stack:
s = o_stack[0] + 1 if len(o_stack) & 1 else 0
else:
if len(o_stack) & 1:
rem_flips = flips - len(o_stack) / 2 - 2
c_len = len(c_stack) - 1
else:
c_len = len(c_stack)
rem_flips = flips - len(o_stack) / 2
if rem_flips == -1:
s = o_stack[0] + 1
elif 2 * rem_flips < c_len:
s = c_stack[c_len - 2 * rem_flips - 1] + 1
else:
if grr and (c_len & 1):
s = (0 if c_len - 2 * rem_flips < 2 else c_stack[c_len - 2 * rem_flips - 2] + 1) + 1
else:
s = (c_stack[0] + 1) if c_len & 1 else 0
result = max(result, i - s + 1)
return result
The solution obtained perfect score.
large tests for solutions finding non-optimal results and extend it naively