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)
}
7 months ago
  • 8da57acFix minor bugs found by the code static ana…
7 months ago
  • caa417fAdd option to configure the malware scanner…
7 months ago
  • 9c86744Modify default value for some of the alert …
7 months ago
  • 84dd39dAdd option to stop sending the failed login…
7 months ago
  • eb05935Add pre-checks for every plugin page for si…
7 months ago
  • d21a062Modify mechanism to ignore files from integ…
7 months ago
  • b1a9169Add developer option to disable failed pass…
7 months ago
  • 4e3ef13Add support for other English and Spanish b…
7 months ago
  • 2d07b4eFix error interception for Firewall API err…
7 months ago
pushed to master at cixtor/slackapi
  • 4a2c1c8Modify data type for methods related to cha…
  • 6716199Add CLI handler for the users.identity API …
  • f9c448dAdd CLI handler for the mpim.open API endpo…
  • 305d1c4Add CLI handler for the mpim.mark API endpo…
  • 8bb89afAdd CLI handler for the mpim.close API endp…
  • 202a017Add CLI handler for the dnd.teamInfo API en…
  • 68819e9Add CLI handler for the dnd.info API endpoi…
  • 9a2b29aAdd CLI handler for the dnd.endSnooze API e…
  • e7dc86aAdd CLI handler for the dnd.setSnooze API e…
  • 111c53fAdd CLI handler for the dnd.endDnd API endp…
  • cdb620dFix token usage when there are no extra par…
  • View comparison for these 11 commits
7 months ago
pushed to master at cixtor/slackapi
7 months ago
  • 6497e80Remove unnecessary automatic blacklisting o…
7 months ago
opened pull request Sucuri/sucuri-wordpress-plugin#40
Fix multiple bugs with the API calls and queue system
18 commit with 793 additions and 293 deletion
7 months ago
7 months ago
7 months ago
  • 38cc02aModify timing for the dashboard alerts afte…
7 months ago
  • 350c074Fix infinite loop with email alerts and SMT…
7 months ago
  • acff4aaFix detection of base URL with built-in fun…
7 months ago
7 months ago
7 months ago
7 months ago
7 months ago
opened pull request Sucuri/sucuri-wordpress-plugin#39
Add queue system for the security logs and cache improvement
5 commit with 517 additions and 541 deletion
7 months ago
7 months ago
  • 4c51445Fix static function call of non-static Site…
7 months ago
7 months ago
  • af47581Add changelog to release version 1.8.6
7 months ago
opened pull request Sucuri/sucuri-wordpress-plugin#38
Add changelog to release version 1.8.5
6 commit with 4062 additions and 1841 deletion
7 months ago
  • dc1a05aAdd changelog to release version 1.8.5
7 months ago
Do you have a project idea? Let's make it together!