Task — Longest parenthesis

You are given a string containing only ( and ). Write a script to find the length of the longest valid parenthesis.

Examples

Example 1
Input: $str = '(()())'
Output: 6
Valid Parenthesis: '(()())'

Example 2
Input: $str = ')()())'
Output: 4
Valid Parenthesis: '()()' at positions 1-4.

Example 3
Input: $str = '((()))()(((()'
Output: 8
Valid Parenthesis: '((()))()' at positions 0-7.

Example 4
Input: $str = '))))((()('
Output: 2
Valid Parenthesis: '()' at positions 6-7.

Example 5
Input: $str = '()(()'
Output: 2
Valid Parenthesis: '()' at positions 0-1 and 3-4.

Analysis

Inspection of the examples shows that a valid parenthesis (vp) comprises (x) where x = zero or more other vps.

The above definition leads nicely to a recursive solution, which is why I didn't do that. My reasoning is that recursion is quite expensive in Perl, and there is a solution that just makes a single pass along the string.

In that solution I pass along the string maintaining a count of $height, which is the number of opening '(' minus the number of closing ')' seen so far. (I used 'height' because I thought of it as a graph).

When I encounter a '(' I increment $height, and push the current index of the '(' onto @opens; this is therefore a stack of all the '(' indices potentially waiting for a ')'.

When I encounter a ')' I decrement $height, and then:

If $height is still >= 0 I pop the last element from @opens, which is the start of a vp ending at the current position. I check the length of this vp against the longest length so far, and if it is equal to or better than that one I save it as potential result.

But if $height is -1, this is a ')' without a matching '(', and so none of the stacked @opens can be the start of a vp. I therefore set @opens = () and continue.

There is a slight snag to this. The above analysis will result in '()()' being correctly identified as two vps of length 2. However, it is also a single vp of length 4, which ought to be the solution. So whenever I find a vp which starts immediately after the preceding one ends, I add the preceding length to the current length. To do that, I have saved the parameters of the immediately preceding vp in %previous.

I tried my solution on a string of a million random '(' and ')' and it completed in 2 seconds with:

648408 at (319070 .. 967477)

I'm pretty sure a recursive solution would take orders of magnitude longer or run out of memory.

Lastly, there may well be a solution using some of the more advanced features of regular expressions, but I'm doubtful that that would be faster than my solution. But I may be proved wrong.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2025-11-03
use utf8;     # Week 346 - task 1 - Longest parenthesis
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

longest_parenthesis('(()())');
longest_parenthesis(')()())');
longest_parenthesis('((()))()(((()');
longest_parenthesis('))))((()(');
longest_parenthesis('()(()');
longest_parenthesis('))');
longest_parenthesis('()()()()()');
longest_parenthesis(')))())))');

sub longest_parenthesis {
    
    my (@parens, $best, $explain, $start, $i, $length, 
        $height, @opens, $this, %previous);
    
    # initialise
    @parens = split('', $_[0]);
    @opens = ();
    $best = $start = $height = 0;
    $explain = '';

    # loop over string
    for $i (0 .. $#parens) {
        $this = $parens[$i];
        
        # found ( - record as start
        if ($this eq '(') {
            push(@opens, $i);
            $height ++;
            
        # found )
        } elsif ($this eq ')' and $height > 0) {
            $height --;
            
            # ( and ) match
            unless ($height < 0) {
                $start = pop(@opens);
                
                # check for this being the longest
                $length = $i - $start + 1;
                if (defined $previous{end} and $start == $previous{end} + 1) {
                    $length += $previous{length};
                    $start = $previous{start};
                }
                
                # record info
                if ($length >= $best) {
                    $explain = '' if $length > $best;
                    $best = $length;
                    $explain .= qq[($start .. $i), ];
                    %previous = (start => $start, length => $length, end => $i);
                }
            
            # unmatched ) - forget all previous starts
            } else {
                @opens = ();
                $start = $i + 1;
            }
        }       
    }
    
    say qq[\nInput:  '$_[0]'];
    say qq[Output: ] . ($best > 0 ? qq[$best at ] . substr($explain, 0, -2) : 'none');
}

Output

Input:  '(()())'
Output: 6 at (0 .. 5)

Input:  ')()())'
Output: 4 at (1 .. 4)

Input:  '((()))()(((()'
Output: 8 at (0 .. 7)

Input:  '))))((()('
Output: 2 at (6 .. 7)

Input:  '()(()'
Output: 2 at (0 .. 1), (3 .. 4)

Input:  '))'
Output: none

Input:  '()()()()()'
Output: 10 at (0 .. 9)