13
\$\begingroup\$

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 ).

\$\endgroup\$
16
  • \$\begingroup\$ Can the input be taken as a list of, say, 0 and 1 or 1 and -1 standing in for parentheses? \$\endgroup\$ Feb 28 at 4:02
  • \$\begingroup\$ I guess so, no? because parenthesis itself due to permutation \$\endgroup\$ Feb 28 at 4:09
  • 1
    \$\begingroup\$ @lesobrod This statement is just part of the recursive definition of a valid string. But since the length of an empty string is 0, the expected answer is indeed the same as for an entirely invalid string. \$\endgroup\$
    – Arnauld
    Feb 28 at 7:16
  • 13
    \$\begingroup\$ I'm confused why the title is Shortest Valid Parentheses but required to find the length of the longest substring that forms a valid pair of parentheses ? \$\endgroup\$
    – EzioMercer
    Feb 28 at 8:41
  • 4
    \$\begingroup\$ @UndoneStudios Better title is Longest Valid Parantheses \$\endgroup\$
    – EzioMercer
    Mar 1 at 15:19

18 Answers 18

10
\$\begingroup\$

Excel (ms365), 136 bytes

enter image description here

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!

\$\endgroup\$
0
6
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ s=>s.reduce((q,c,i)=>(p=c>'('?i-s.pop():s.push(i+~p)*0)>q?p:q,p=0) - 66 bytes if input is array of characters \$\endgroup\$
    – EzioMercer
    Mar 4 at 22:25
  • 1
    \$\begingroup\$ @EzioMercer ")()()" should be 4 \$\endgroup\$
    – tsh
    Mar 5 at 2:48
6
\$\begingroup\$

APL(Dyalog Unicode), 46 bytes SBCS

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

Try it on APLgolf!

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

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Since you don't care about the order of substrings, ⍳∘≢ can be a grade instead. \$\endgroup\$
    – ovs
    Feb 28 at 7:18
5
\$\begingroup\$

Vyxal, 7 bytes

ǎ~øβÞGL

Try it Online!

Explained

ǎ~øβÞGL
ǎ       # substrings of the input
 ~øβ    # with only those with balanced brackets kept
    ÞGL # get the length of the longest substring that remains
\$\endgroup\$
5
\$\begingroup\$

BQN, 30 bytesSBCS

{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.

\$\endgroup\$
2
  • \$\begingroup\$ Curious, does BQN not have something like rplc or a regex, or was this approach just shorter? \$\endgroup\$
    – Jonah
    Feb 28 at 15:33
  • 1
    \$\begingroup\$ @Jonah BQN doesn't have string replacement, you would have to do something based on string search (E.) which is probably a lot longer. There is a also no ^:_, so you have to use recursion. But maybe a recursive solution removing only one pair of matching brackets at a time could be competitive \$\endgroup\$
    – ovs
    Feb 28 at 19:34
5
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

><> (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

enter image description here

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

\$\endgroup\$
4
\$\begingroup\$

J, 35 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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ rplc&('()';'')^:_ can be rplc&('()';'')^:#, which can be shortened to #rplc&('()';'')]. \$\endgroup\$
    – ovs
    Feb 28 at 7:22
  • \$\begingroup\$ Nice catch! Thanks @ovs. \$\endgroup\$
    – Jonah
    Feb 28 at 15:32
3
\$\begingroup\$

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)
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
0
1
\$\begingroup\$

Charcoal, 35 bytes

⊞υ⁰≔⮌υθFS«≦⊕υ≡ι(⊞υ⁰¿∧⊟υυ⊞θ⌊υ⊞υ⁰»I⌈θ

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.

FS«

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.

»I⌈θ

Output the maximum balanced substring length found.

\$\endgroup\$
1
\$\begingroup\$

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
  }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.