Longest Valid Parentheses

Question

Given a string of parentheses ( and ), find the length of the longest substring that forms a valid pair of parentheses.

Valid pairs of parentheses are defined as the following:

An empty string is a valid pair of parentheses. If s is a valid pair of parentheses, then (s) is also a valid pair of parentheses. If s and t are both valid pairs of parentheses, then st is also a valid pair of parentheses. For example, the longest valid substring of (()()) is (()()), with length 6.

Write a function or program that takes a string of parentheses as input and outputs the length of the longest valid substring.

Example:

Input: (()()) Output: 6

Input: )()()) Output: 4

Input: ()(()) Output: 6

Input: ()(() Output: 2

Input: )) Output: 0

Input: Output: 0

Code golf rules:

Write a function or program that takes a string of parentheses as input and outputs the length of the longest valid substring, using as few characters as possible.

The score of your solution will be the number of characters in your code. The solution with the shortest code wins. In case of ties, the earlier submission wins.

You can assume the input string contains only the characters ( and ).

Answer 1

Excel (ms365), 136 bytes

Formula in B1:

=LET(x,ROW(A:A),y,SCAN(")"&A1,x,LAMBDA(a,b,SUBSTITUTE(a,"("&REPT("|",(b-1)*2)&")",REPT("|",b*2)))),MAX(ISNUMBER(FIND(REPT("|",x),y))*x))

The idea here is that we create a loop to iteratively replace the fundamental base of balanced paranthesis, "()". The 1st replacement is simply "||". Next we replace all occurences of "(||)", with "||||" etc, untill we can't replace any more. Finally we calculate the longest occurence of consecutive "|" characters.

Yes, 136 bytes is a lot though!

Answer 2

JavaScript (ES6), 95 bytes

f=(s,S=s)=>s!=(s=s.split`()`.join``)?f(s,S):s?Math.max(f(S.slice(1)),f(S.slice(0,-1))):S.length

Try it online!

Answer 3

JavaScript (Node.js), 75 bytes

s=>[...s].map((c,i)=>q=(p=c>'('?i-a.pop():a.push(i+~p)*0)>q?p:q,q=p=a=[])|q

Try it online!

Or 71 bytes if we take input as array of characters.

Let us denote the input sting as s. Let use denote the length of longest valid parentheses string which ends by s[i] as d[i]. Then question is asking for the greatest value in array d.

• If s[i] is (, d[i] is 0
  • It is trivial, as the last ( does not have a matching ) and therefore be invalid.
• If s[i] is ), we first find out the matching ( for it
  • If there is no matching ( for it, d[i] is 0
  • If s[j] is some ( character which match s[i], then s[j..i] is a valid parentheses string. And d[i]=i-j+1+d[j-1].

To find out matching ( for s[i], we use a stack named a in the source code, and push j-1-d[j-1] into it.

Answer 4

APL(Dyalog Unicode), 46 bytes ^SBCS

(⌈/≢¨×{0(∧.≤∧=∘⊃∘⌽)+\-⌿'()'∘.=⍵}¨)⍤⊃⍳∘≢,.(,/)⊂

Try it on APLgolf!

⊃⍳∘≢,.(,/)⊂                 substrings
{0(∧.≤∧=∘⊃∘⌽)+\-⌿'()'∘.=⍵}¨ map balanced?
≢¨×                         times lengths
⌈/                          max

Answer 5

Raku, 30 bytes

{m:g/(\(<~~>\))*/>>.chars.max}

Try it online!

Uses a recursive regex to find all sets of balanced parenthesis, then takes the maximum length of those strings.

Explanation

{                            }   # Anonymous codeblock
 m:g/           /                # Find all non-overlapping matches in string
     (        )*                  # Zero or more of 
      \(    \)                      # Literal brackets
        <~~>                        # Containing balanced parenthesises
                >>.chars         # Map to length of string
                        .max     # Maximum

Answer 6

BQN, 30 bytes^SBCS

{0⌈´∾1+/¨0(=∧∧`¨∘≤)+`¨↓¯1⋆𝕩-@}

Run online!

¯1⋆𝕩-@ Map ( to 1 and ) to ¯1.
+`¨↓ Take the cumulative sum of each suffix.
0(=∧∧`¨∘≤) For each value in each suffix, is it equal to 0 and are all preceding values non-negative?
∾1+/¨ All 1-based indices of 1s.
0⌈´ Take the maximum or 0 if there is no such index.

Answer 7

><> (Fish), 135 bytes

0:i:0(?v$6p1+00. ;n+1-~~.?&52~\
@$:@02.\~~1-:0>:
>0&:6g2%2*1-&+:0(?v&1-$:@$:@)?^22.
>1+$1+$:{:})?v$d1.   
 .1f0v!?:-1-$/ .55/
^~~~ \0n;

Try it

Uses the classic paste the input on the source block for easy indexing trick

Answer 8

Vyxal, 7 6 bytes

ǎ~øβ@G

Try it Online!

-1 byte thanks to modern innovations like vectorising length

Explained

ǎ~øβ@G­⁡​‎‎⁡⁠⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁡‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁣‏⁠‎⁡⁠⁤‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌­
 ~      # ‎⁡Get all
ǎ       # ‎⁢substrings of the input
 ~      # ‎⁣where
  øβ    # ‎⁤the brackets are balanced.
    @G  # ‎⁢⁡Get the longest length
💎

Created with the help of Luminespire.

Answer 9

J, ³⁵ 34 bytes

[:>./@,(#*''-:#rplc&('()';'')])\\.

Try it online!

-1 thanks to ovs

• For every every substring...
• Continually replace () with the empty string
• If the result is the empty string, return the length, otherwise 0
• Max of all results

Answer 10

05AB1E, 13 bytes

Œʒ„()õ:õQ}éθg

Try it online or verify all test cases

Explanation:

Π       # Get all substrings of the (implicit) input
 ʒ       # Filter it by:
  „()    #  Push string "()"
     õ:  #  Keep replacing "()" with "" until it's no longer possible
  õQ     #  Check if what remains is an empty string ""
 }é      # After the filter: sort the remaining strings by length
   θ     # Pop and keep the last/longest
    g    # Pop and push its length
         # (which is output implicitly as result)

Answer 11

Retina 0.8.2, 39 bytes

M!`((\()|(?<-2>\)))+(?(2)^)
.
.
O^`
\G.

Try it online! Link includes test cases. Explanation:

M!`((\()|(?<-2>\)))+(?(2)^)

Find all nontrival substrings of balanced parentheses, using .NET's balancing groups; ?<-2> prevents the number of matched )s from exceeding the number of (s seen so far, while the ?(2) ensures that there are no unmatched (s.

.
.

Take the length of each substring in unary.

O^`

Sort in reverse order.

\G.

Output the first length or 0 if there were no matches.

Answer 12

JavaScript, 130 bytes

s=>[...s,0].map((_,i,a)=>a.map((_,j,$,S=s.slice(i,j),b=0)=>{for(l of S)if((l==')'?--b:++b)<0)break;r=b|r>(l=S.length)?r:l}),r=0)|r

Try it:

f=s=>[...s,0].map((_,i,a)=>a.map((_,j,$,S=s.slice(i,j),b=0)=>{for(l of S)if((l==')'?--b:++b)<0)break;r=b|r>(l=S.length)?r:l}),r=0)|r

;[
  '(()())', // 6

  ')()())', // 4

  '()(())', // 6

  '()(()', // 2

  '))', // 0

  '', // 0
].forEach(s=>console.log(f(s)))

Algorithm:

Take the all substrings of string and check if it is balanced parentheses. If yes, then check if the length of substring is maximum? If yes then update the max value. Else don't change the max value

Answer 13

vim, 72 bytes

o:s/(\(a*\))/a\1a/g<C-v><CR>@"<ESC>v0dk@":s/[()]/<C-v><CR>/g
:g/^/.!wc -c
:%!sort -nr
jdG<C-x>

Annotated

o:s/(\(a*\))/a\1a/g<C-v><CR>@"<ESC>   # insert command that recursively replaces (a*) with aa*a as long as there are matches
v0dk@"                                # pulls the above command into register " and invokes it. (Any resemblance to the word "vodka" is entirely coincidental.)
:s/[()]/<C-v><CR>/g                   # Any parentheses that remain are invalid. Split the string into separate lines with them as delimiters
:g/^/.!wc -c                          # strlen of each line (including newline)
:%!sort -nr                           # put the largest number on top
jdG<C-x>                              # delete the rest, decrement the newline away

<C-v> is 0x16, <C-x> is 0x18 <ESC> is 0x1b, and <CR> is 0x0d.

Try it online!

Answer 14

Nekomata, 16 bytes

qe7%3%∫:çlR≥¤#aṀ

Attempt This Online!

qe7%3%∫:çlR≥¤#aṀ
q                     Non-deterministically choose a contiguous subsequence
 e7%3%                Convert the subsequence to a list of 2's and 0's
      ∫               Take the cumsum
       :              Duplicate
        çl            Prepend 0 and get the last item
          R           Range from 1 to this number
           ≥¤         Compare the cumsum and this range;
                        fail if the two list has different length,
                        or if any item in the cumsum is less than
                        the corresponding item in the range
             #        Get the length
              a       Get all possible values
               Ṁ      Get the maximum

Answer 15

Jelly, 13 bytes

ẆœṣØ(F$ÐLÐḟẈṀ

Try it online!

Uses Kevin Cruijssen's 05AB1E algorithm, be sure to give them an upvote!

How it works

ẆœṣØ(F$ÐLÐḟẈṀ - Main link. Takes a string S on the left
Ẇ             - All contiguous sublists of S
         Ðḟ   - Filter sublists, keeping those which return [] under:
      $       -   Group the last 2 links as a monad f(W):
   Ø(         -     Yield "()"
 œṣ           -     Split W on "()"
     F        -     Flatten
       ÐL     -   Repeatedly apply f(W) until a fixed point
           Ẉ  - Lengths of those remaining
            Ṁ - Maximum

Answer 16

Japt -h, 14 bytes

Outputs undefined instead of 0 (pending confirmation).

ã ke"%(%)" mÊÍ

Try it

9 bytes

This version takes input as a string of 1s & 0s, representing ( & ) respectively, which the comments on the challenge would seem to allow.

ã keA mÊÍ

Try it

ã ke"%(%)" mÊÍ     :Implcit input of string
ã                  :Substrings
  k                :Remove items that return truthy (non-empty string)
   e               :  Recursively replace
    "%(%)"         :  RegEx /\(\)/ (or A=10, in the second version)
           m       :Map
            Ê      :  Length
             Í     :Sort
                   :Implicit out output of last element

Answer 17

Haskell + hgl, 13 bytes

xMl<fl blp<cG

blp isn't on ato yet ...

Explanation

• cG get all contiguous substrings.
• fl blp filter the ones that are balanced.
• xMl get the length of the longest one.

Reflection

This is pretty short but ...

• There could definitely be functions for

  • "prefixes such that"
  • "suffixes such that"
  • "infixes such that"

  The final one would be useful here.

Answer 18

Charcoal, 35 bytes

⊞υ⁰≔⮌υθＦＳ«≦⊕υ≡ι(⊞υ⁰¿∧⊟υυ⊞θ⌊υ⊞υ⁰»Ｉ⌈θ

Try it online! Link is to verbose version of code. Explanation:

⊞υ⁰

Start with no characters at the current indent level.

≔⮌υθ

Also start with a maximum balanced run length of zero.

ＦＳ«

Loop over the input characters.

≦⊕υ

Increase the characters at all depths.

≡ι(⊞υ⁰

If this is a ( then start a new depth level. Otherwise:

¿∧⊟υυ

Remove a depth level, and if there is still at least one level left, then...

⊞θ⌊υ

... push the length of the deepest level left to the list of found balanced substring lengths, otherwise...

⊞υ⁰

.. the ) was unbalanced, so start a new empty indent level.

»Ｉ⌈θ

Output the maximum balanced substring length found.

Answer 19

Scala, 242 bytes

I first know replaceAllLiterally in scala, it saved several bytes.

---

Golfed version, try it online!

def f1(s:String):Int={f(s,s)};def f(s:String,S:String):Int={if(s!=s.replaceAllLiterally("()","")){f(s.replaceAllLiterally("()",""),S)}else if(s.nonEmpty){val left=S.dropRight(1);val right=S.drop(1);math.max(f1(left),f1(right))}else{S.length}}

Ungolfed version, try it online!

object Main {
  def f1(s: String): Int = {f(s,s)}
  def f(s: String, S: String ): Int = {
    if (s != s.replaceAllLiterally("()", "")) {
      f(s.replaceAllLiterally("()", ""), S)
    } else if (s.nonEmpty) {
      val left = S.dropRight(1)
      val right = S.drop(1)
      math.max(f1(left), f1(right))
    } else {
      S.length
    }
  }

  def main(args: Array[String]): Unit = {
    println(f1("(()())")) // 6
    println(f1(")()())")) // 4
    println(f1("()(())")) // 6
    println(f1("()(()" )) // 2
    println(f1("))"    )) // 0
    println(f1(""      )) // 0
  }
}

Answer 20

Python 3, 104 bytes

f=lambda s:max(f(s[1:]),f(s[:-1]))if g(s)else len(s)
g=lambda s:g(s.replace('()',''))if'()'in s else''<s

Try it online!