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.

This post blends practical implementation knowledge with sophisticated algorithms. Peter demonstrates a solid foundation in computer science and carefully weighs the pros and cons of various strategies.

This review may cover either or both challenges for this week.

Try it 

Try running the script with any input:

Your $string =

example: ((()))

⤡

#!/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');
}

30 lines of code

Output from script

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)