CtCI - Balanced Parenthesis

CtCI - Balanced Parenthesis

Determine if there is a parenthesis balance in a given string:

a(bcd)d         => true
(kjds(hfkj)sdhf => false
(sfdsf)(fsfsf   => false
{[]}()          => true
{[}]            => false

What we have here is a basic counting problem, we are given a list of characters and we have to determine if a group of two exists. In this specific case we have to count if the number of opening parenthesis is the same as the number of closing parenthesis, if the different is an odd number we can consider the result as False otherwise True.

func solution(word string) bool {
    var opening int
    var closing int

    for _, char := range word {
        if char == '(' {
            opening++
        } else if char == ')' {
            closing++
        }
    }

    return ((opening-closing)%2 == 0)
}

We have to consider that the number of opening parenthesis might be lower than the number of closing parenthesis, a subtraction would generate a negative number so we have to pass the result through an absolute number generator before we compare the module.

func solution(word string) bool {
    var opening int
    var closing int

    for _, char := range word {
        if char == '(' {
            opening++
        } else if char == ')' {
            closing++
        }
    }

    result = opening - closing

    if result < 0 {
        result *= -1
    }

    return (result%2 == 0)
}

Now, what happens if there is no parenthesis at all? We will get an opening = 0 and closing = 0 which after the modulation we can an even number because 0 == 0 but as we can see in the expected output above we need to consider this case as False. This means that before we check if the result of the subtraction is an even number we must check if both the opening and closing are greater than zero.

func solution(word string) bool {
    var opening int
    var closing int

    for _, char := range word {
        if char == '(' {
            opening++
        } else if char == ')' {
            closing++
        }
    }

    if opening == 0 || closing == 0 {
        return false
    }

    result = opening - closing

    if result < 0 {
        result *= -1
    }

    return (result%2 == 0)
}

Everything seems correct, and even all the test cases pass, but what happens to the code when we pass this string )))(((? It has the same amount of opening and closing parenthesis but they are not balanced because the closing characters are positioned before the opening ones, we need a better code for this, and will probably need to refactor.

The iterator is working as expected but the logic inside is not, we can continue counting the opening parenthesis but counting the closing characters seems unnecessary, here is why: A balanced parenthesis is one where for every opening character at index M there is a closing one at index M+N where N>M. We will rewrite the code to count the opening parenthesis and for each closing character we will subtract one. If we find that the opening variable is less than zero we can assume the string is not balanced.

func solution(word string) bool {
    var opening int
    var foundone int

    for _, char := range word {
        if char == '(' {
            opening++
            foundone++
        } else if char == ')' {
            opening--
            foundone++

            if opening < 0 {
                return false
            }
        }
    }

    return (foundone > 0 && opening == 0)
}
Do you have a project idea? Let's make it together!