On Sunday, November 24, 2019, I participated in the ASU SoDA Coding Challenge VI. The ASU Software Developer’s Association (SoDA) is a club that is dedicated to teaching aspiring programmers how to solve complex problems that will prepare them for industry. The club runs recruiting events, Hackathons, Interview Prep sessions, and other activities that I have personally found invaluable during my first semester at ASU. I would strongly recommend anyone with a remote interest in computer science to join the club.
The SoDA Coding Challenge had 15 questions which were divided into three categories of three questions based on their respective difficulty levels. The Easy Questions, the Medium Questions, and the Hard Questions were made available to the contestants through Google Forms, and participants would have proctors manually check their code to make sure their programs worked.
Easy Question #3 concerns determining the length and the frequency of the longest regular bracket subsequence in a string of parentheses. The question reads:
ASU SoDA Coding Challenge VI Easy Question 3: Longest Bracket Subsequence
This is yet another problem dealing with regular bracket sequences.
We should remind you that a bracket sequence is called regular, if by inserting «+» and «1» into it we can get a correct mathematical expression. For example, sequences «(())()», «()» and «(()(()))» are regular, while «)(», «(()» and «(()))(» are not.
You are given a string of «(» and «)» characters. You are to find its longest substring that is a regular bracket sequence. You are to find the number of such substrings as well.
Input:
The first line of the input file contains a non-empty string, consisting of «(» and «)» characters. Its length does not exceed 10^6.
Output:
Print the length of the longest substring that is a regular bracket sequence, and the number of such substrings. If there are no such substrings, write the only line containing "0 1".
Test Cases:
input
)((())))(()())
output
6 2
input
))(
output
0 1
My solution for this problem was very messy as I used manual string parsing in Python rather than RegEx or some other method. Here’s my solution:
Solution #1: O(n^2) Approach
We simply search for every regular bracket subsequence from each starting open parentheses. For each starting point, we count from that parentheses, adding 1 for open parentheses and subtracting 1 for closed parentheses. If the total is ever negative, we can stop searching for the given start point. If the total is ever 0, we have found a regular subsequence. In this manner, we can find and count all maximal regular bracket subsequences in O(n^2) time complexity. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
SoDA Coding Challenge VI Easy Problem #3
https://docs.google.com/document/d/1E_8BtPkGH5iQSBVOxr_lZpjrS5pToaWtDBS1WEZTxWw/edit
'''
import time
import sys
for x in sys.stdin:
if(x[len(x)-1]=='\n'):
x = x[0:len(x)-1]
myInput = x
def maxSubsequence(par):
maxFound = 0
total = 0
times = 0
start = []
for i in range(len(par)):
if(par[i]=="("):
start.append(i)
for i in start:
total = 0
v = 0
a = par[i:]
for x in a:
v+=1
if x=="(":
total+=1
elif x==")":
total-=1
if(total<0):
break
if(total==0):
if(v==maxFound):
times+=1
elif(v>maxFound):
times = 1
maxFound = v
if(maxFound == 0):
return "0 1"
else:
return str(maxFound) + " " + str(times)
start = time.time()
print maxSubsequence(myInput)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
12 1
--- 2.71797180176e-05 seconds ---
for input of myInput = ")((())))(()())))))(((())))(()))()"
'''
And with that, we’re done. While this may have been efficient enough for the purposes of the coding challenge, I am sure that an O(n) solution exists, so I may come back to this problem at some point.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 