/* package whatever; // don't place package name! */
class CountLongestBalanced {
public static void main
(String[] args
) { String[] testCases
= {"(()",
")()())",
"((()()",
"((()(()()",
"(())(()",
"())()()"}; System.
out.
printf("%s -> %d\n", s, countLongestBalanced
(s,
0)); }
}
static int countLongestBalanced
(String str,
int start
) { if ((str.length() - start) <= 1) return 0;
int longestN = 0;
int curN = 0;
int count = 0;
int lastRunStart = 0;
for (int i = start; i < str.length(); ++i) {
switch(str.charAt(i)) {
case '(': ++count; break;
case ')': --count; break;
default: continue;
}
++curN;
if (count == 0) {
longestN
= Math.
max(curN, longestN
); lastRunStart = i + 1;
} else if (count < 0) {
//bad balance, start over
curN = 0;
count = 0;
lastRunStart = i + 1;
}
}
if (count
== 0) longestN
= Math.
max(curN, longestN
); else if (count > 0) { //"save" unbalance for extra open pars by skipping them
int i = lastRunStart;
for (; i < str.length() && count > 0; ++i) {
if (str.charAt(i) == '(') --count;
else if (str.charAt(i) == ')') ++count;
}
if (i < str.length()) {
//Note: this will be called only once (no deeper recursion)
longestN
= Math.
max(longestN, countLongestBalanced
(str, i
)); }
}
return longestN;
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKCmNsYXNzIENvdW50TG9uZ2VzdEJhbGFuY2VkIHsKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKICAgICAgICBTdHJpbmdbXSB0ZXN0Q2FzZXMgPSB7IigoKSIsICIpKCkoKSkiLCAiKCgoKSgpIiwgIigoKCkoKCkoKSIsICIoKCkpKCgpIiwgIigpKSgpKCkifTsKICAgICAgICBmb3IgKFN0cmluZyBzIDogdGVzdENhc2VzKSB7CiAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRmKCIlcyAtPiAlZFxuIiwgcywgY291bnRMb25nZXN0QmFsYW5jZWQocywgMCkpOwogICAgICAgIH0KICAgIH0KCiAgICBzdGF0aWMgaW50IGNvdW50TG9uZ2VzdEJhbGFuY2VkKFN0cmluZyBzdHIsIGludCBzdGFydCkgewogICAgICAgIGlmICgoc3RyLmxlbmd0aCgpIC0gc3RhcnQpICA8PSAxKSByZXR1cm4gMDsKICAgICAgICBpbnQgbG9uZ2VzdE4gPSAwOwogICAgICAgIGludCBjdXJOID0gMDsKICAgICAgICBpbnQgY291bnQgPSAwOwogICAgICAgIGludCBsYXN0UnVuU3RhcnQgPSAwOwogICAgICAgIGZvciAoaW50IGkgPSBzdGFydDsgaSA8IHN0ci5sZW5ndGgoKTsgKytpKSB7CiAgICAgICAgICAgIHN3aXRjaChzdHIuY2hhckF0KGkpKSB7CiAgICAgICAgICAgICAgICBjYXNlICcoJzogKytjb3VudDsgYnJlYWs7CiAgICAgICAgICAgICAgICBjYXNlICcpJzogLS1jb3VudDsgYnJlYWs7CiAgICAgICAgICAgICAgICBkZWZhdWx0OiBjb250aW51ZTsKICAgICAgICAgICAgfQogICAgICAgICAgICArK2N1ck47CiAgICAgICAgICAgIGlmIChjb3VudCA9PSAwKSB7CiAgICAgICAgICAgICAgICBsb25nZXN0TiA9IE1hdGgubWF4KGN1ck4sIGxvbmdlc3ROKTsKICAgICAgICAgICAgICAgIGxhc3RSdW5TdGFydCA9IGkgKyAxOwogICAgICAgICAgICB9IGVsc2UgaWYgKGNvdW50IDwgMCkgewogICAgICAgICAgICAgICAgLy9iYWQgYmFsYW5jZSwgc3RhcnQgb3ZlcgogICAgICAgICAgICAgICAgY3VyTiA9IDA7CiAgICAgICAgICAgICAgICBjb3VudCA9IDA7CiAgICAgICAgICAgICAgICBsYXN0UnVuU3RhcnQgPSBpICsgMTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBpZiAoY291bnQgPT0gMCkgbG9uZ2VzdE4gPSBNYXRoLm1heChjdXJOLCBsb25nZXN0Tik7CiAgICAgICAgZWxzZSBpZiAoY291bnQgPiAwKSB7IC8vInNhdmUiIHVuYmFsYW5jZSBmb3IgZXh0cmEgb3BlbiBwYXJzIGJ5IHNraXBwaW5nIHRoZW0KICAgICAgICAgICAgaW50IGkgPSBsYXN0UnVuU3RhcnQ7CiAgICAgICAgICAgIGZvciAoOyBpIDwgc3RyLmxlbmd0aCgpICYmIGNvdW50ID4gMDsgKytpKSB7CiAgICAgICAgICAgICAgICBpZiAoc3RyLmNoYXJBdChpKSA9PSAnKCcpIC0tY291bnQ7CiAgICAgICAgICAgICAgICBlbHNlIGlmIChzdHIuY2hhckF0KGkpID09ICcpJykgKytjb3VudDsKICAgICAgICAgICAgfQogICAgICAgICAgICBpZiAoaSA8IHN0ci5sZW5ndGgoKSkgewogICAgICAgICAgICAJLy9Ob3RlOiB0aGlzIHdpbGwgYmUgY2FsbGVkIG9ubHkgb25jZSAobm8gZGVlcGVyIHJlY3Vyc2lvbikKICAgICAgICAgICAgICAgIGxvbmdlc3ROID0gTWF0aC5tYXgobG9uZ2VzdE4sIGNvdW50TG9uZ2VzdEJhbGFuY2VkKHN0ciwgaSkpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHJldHVybiBsb25nZXN0TjsKICAgIH0KfQ==