https://kotlinlang.org logo
Join Slack
Powered by
Isn't the actual issue that the length should be `...
# announcements
k
Isn't the actual issue that the length should be 
j - i + 1
?
w
if (balance == 0 && j-1 > longest) longest = j-i+1
like this?
k
Well try it simple smile
w
Nope no dice...it now returns 2 no matter the input string
was returning 1 before
maybe I'll incorporate the changes you suggested and post it again
k
Can you give another example input?
Yea go ahead.
w
Copy code
fun longestValidParentheses(s: String): Int {
    var longest = 0
    for (i in 0 until s.length) {
        var balance = 0
        for (j in 0 until s.length) {
            if (s[j] == '(') balance += 1 else balance -= 1
            if (balance < 0) break
            if (balance == 0 && j-1 > longest) longest = j-i+1
        }
    }
    return longest
}

fun main(args: Array<String>) {
    println(longestValidParentheses("(()"))
    println(longestValidParentheses("))))())(())()))(()()(())(())()))(((()()))()()))(())(())()())()(()())((()(((())()())(()())(())((()))))())()))()(())))())()))(()))((()())((()(())))(()))))))))((())(()()((())()()(()))))(((()(())))())))()())))())()()())()(())()(((())()))()()())))()())))()((((((())((())))((())())(((()())())()((((((()())((()()(())(()))(()())()))()(()(()())(()))((())((())))))()()))))()())()))))((((())(())))((()))(()()()()()((())((((())())()())()())(()(()()))())(((()())(()))()))(())()((()(())))))()())())()()(())))((())()()()))(())((()())))))((()((((()(((())()))))(()))()()))(()(())(()((()()()))))()))()()(((()()(())())()(())(()()()))()(()())))()((()((()))))())()(())()(()()((()()())(((())((())))(()())))()))()()())()))((()))(((()()()((()))))()()()))()))())())))))())()))(()))))(()()()))()((())))((())))()))(()()()()()()(()))())())(((())))(())(()(()())((()()()()))()()(()()))(()())(()()()((()()(((()(()((()((((()((())((()()))))))()())())(()(())()((((()()()()()))))()())()((())))))))()(((()())))()(()()(()()()()))()((((()((())(())))())))(()()()())()))))))((()))())((())(()(()(((()()()((((()()))())()())()())()))))())()(((()))))()()())))(())())))(())())((()))(())))(((()()))((((()))(()()))())((()())(()))(()(())(()(()))((((((()()(()()(()))()(()(())((((((((()(()())((())))())()())(()(()()))))(()(()()()))(()((()(((())((())(())()(()()())(()))())((()((((((())())(())()(()()(()())(())())()()))())(()))(())))()())))()()((()))())()()(())(()())()())())())))()()))((((()((()(())(((())()((())(())())))))()(()))())()))())(((())))))((((()(()()))))(((())(((())((())))))()()))()(()(((((((()))))((()))())()(())()))())())((()))))((())(())))(((())((((()(())(())()(((((())))()))()(()())(()()(())()(((()))())())))()))()()())(("))
}
better?
Copy code
fun longestValidParentheses(s: String): Int {
    var longest = 0
    for (i in 0 until s.length) {
        var balance = 0
        for (j in 0 until s.length) {
            if (s[j] == '(') balance += 1 else balance -= 1
            if (balance < 0) break
            if (balance == 0 && j-i > longest) longest = j-i+1
        }
    }
    return longest
}

fun main(args: Array<String>) {
    println(longestValidParentheses("(()"))
    println(longestValidParentheses("))))())(())()))(()()(())(())()))(((()()))()()))(())(())()())()(()())((()(((())()())(()())(())((()))))())()))()(())))())()))(()))((()())((()(())))(()))))))))((())(()()((())()()(()))))(((()(())))())))()())))())()()())()(())()(((())()))()()())))()())))()((((((())((())))((())())(((()())())()((((((()())((()()(())(()))(()())()))()(()(()())(()))((())((())))))()()))))()())()))))((((())(())))((()))(()()()()()((())((((())())()())()())(()(()()))())(((()())(()))()))(())()((()(())))))()())())()()(())))((())()()()))(())((()())))))((()((((()(((())()))))(()))()()))(()(())(()((()()()))))()))()()(((()()(())())()(())(()()()))()(()())))()((()((()))))())()(())()(()()((()()())(((())((())))(()())))()))()()())()))((()))(((()()()((()))))()()()))()))())())))))())()))(()))))(()()()))()((())))((())))()))(()()()()()()(()))())())(((())))(())(()(()())((()()()()))()()(()()))(()())(()()()((()()(((()(()((()((((()((())((()()))))))()())())(()(())()((((()()()()()))))()())()((())))))))()(((()())))()(()()(()()()()))()((((()((())(())))())))(()()()())()))))))((()))())((())(()(()(((()()()((((()()))())()())()())()))))())()(((()))))()()())))(())())))(())())((()))(())))(((()()))((((()))(()()))())((()())(()))(()(())(()(()))((((((()()(()()(()))()(()(())((((((((()(()())((())))())()())(()(()()))))(()(()()()))(()((()(((())((())(())()(()()())(()))())((()((((((())())(())()(()()(()())(())())()()))())(()))(())))()())))()()((()))())()()(())(()())()())())())))()()))((((()((()(())(((())()((())(())())))))()(()))())()))())(((())))))((((()(()()))))(((())(((())((())))))()()))()(()(((((((()))))((()))())()(())()))())())((()))))((())(())))(((())((((()(())(())()(((((())))()))()(()())(()()(())()(((()))())())))()))()()())(("))
}
minor correction^
k
If only there was a way to make minor corrections to messages 😛
🙃 2
w
I see what you did there haha....duly noted
k
Your second for should be 
for (j in i until s.length)
Which you did right in the first one, but there the problem was the missing 
+1
And the check should be 
j-i+1 > longest
now
w
gotcha!
dumb mistakes on my end
2 questions...is it normally not advised to use forEach?
k
Do you know how ot use the debugger?
w
yeah i do...the one in intellij atleast. did you use that to find the bug?
k
Sometimes it's okay at the end of a sequence chain and if you've just got one line of code, but it's not really a replacement for indexed for loops.
I didn't (because I'm not at a computer), but it could have helped you to find the bug(s).
w
yeah makes sense. its much clearer with a for loop
i guess i was falling into the whole functional programming mantra
k
Yea people often do, the amount of 
?.let
abuse I've seen is crazy.
Its wasn't even more functional, you're still mutating variables.
👍🏼 1
w
okay second question...what would the asymptotic complexity be of this code in your opinion?
k
Interesting exercise: rewrite this is an actual function manner.
w
ouch ive been abusing ?. a lot 😕
could be done with recursion im guessing?
k
Or the 
maxBy
functions.
w
i havent been able to find a best practices in kotlin guide sadly
k
Asymptotic cost would be 
O(n^2)
I think.
w
k
Yeah, that's the one.
w
so it isn't really (asymptotically) an improve over the brute force.
funnily though, leetcode claims this is 99% faster than submissions...while it would time out on simplest brute force
i guess constant factors do matter here
k
What would the bruteforce be?
Yes they really do matter in real life.
w
this one:
Copy code
fun longestValidParentheses(s: String): Int {
        fun isValidParenthese(str: String): Boolean {
            return 0 == str.fold(0, {
                acc: Int, i: Char ->
                var ret: Int = acc
                if (i == '(') ret += 1 else ret -= 1;
                if (acc < 0) ret = 999999999
                ret
            })
        }
        var longest: Int = 0;
        (0..s.length).forEach outer@{ i ->
            (i..s.length).forEach inner@{ j ->
                val substr = s.substring(i, j)
                if (isValidParenthese(substr) && substr.length > longest) longest = substr.length
            }
        }
        return longest
    }
so you can ignore the isValidParenthesis it just works in O(N)
k
That's 
O(n^3)
though, you need to count the 
substring
too.
👍🏼 1
w
the motivation for the faster version was that, as soon as we realize that the brackets cant be balanced (i.e. balance falls below 0) we break out and don't do the needless work in the inner loop
oh yeah you're right...that too.
2 Views
Open in Slack
PreviousNext
Powered by