Skip to content

Instantly share code, notes, and snippets.

@rogeliorv
Created February 22, 2017 20:57
Show Gist options
  • Save rogeliorv/fb0b98ff2438ff93b2dee34e1c492f44 to your computer and use it in GitHub Desktop.
Save rogeliorv/fb0b98ff2438ff93b2dee34e1c492f44 to your computer and use it in GitHub Desktop.
Given a string containing opening braces '(' and closing braces ')' find the index where you have the same number of opening and closing braces
# Codility challenge
# Given a string containing opening braces '(' and closing braces ')'
# Return the index where you have the same number of opening and closing braces
# Example:
# Given '(())' the equilibrium index is two because there are the same number
# of opening brackets to the left as there are closing brackets to the right
#
# Given '(((' the equilibrium index is 0 because there are no opening brackets
# before index 0 and there are 0 closing brackets at that position
#
# Given '))' the equilibrium index is 2 because at position two there are no
# closing brackets to the right and no opening brackets to the left
#
# Given '((()(' the equilibrium index is 1
# This one is easy. Consists on finding the index where the brackets are in a equilibrium.
# We can do the naive way with two loops. But we will be doing the less naive version
# By storing how many opening and closing braces are at each point.
# This can be done with a dictionary or just a couple of lists/arrays
def solution(S):
# This variables will be used to keep track of how many opening or closing
# braces we have ran in. We can do without these by using the value to the
# left or right respectively. Just here for clarity.
soFarLeft = 0
soFarRight = 0
# The data structures that will hold how many brackets we've found so far
lefts = [0] * len(S)
rights = [0] * len(S)
# No opening braces before the first element
lefts.insert(0, 0)
# No closing braces after the last element
rights.append(0)
for leftIndex in range(1, len(S)+1):
rightIndex = len(S) - leftIndex
if S[leftIndex-1] == '(':
soFarLeft += 1
if S[rightIndex] == ')':
soFarRight += 1
lefts[leftIndex] = soFarLeft
rights[rightIndex] = soFarRight
print lefts
print rights
for index, (left, right) in enumerate(zip(lefts, rights)):
if left == right:
return index
return result
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment