File Parentheses.h

↰ Parent directory (ADS/string)

The longest balanced strings of parentheses inside a text of n characters, where open and close are the two parentheses and every other character is neither.

Definition (ADS/string/Parentheses.h)

Detailed Description

  • longestBalancedSubsequence(): the longest subsequence that is balanced. A scan matches each close with the nearest open still unmatched before it, which never loses a pair (an exchange argument), so the length is twice the number of pairs matched: :math:` Theta( n ) ` time and O( 1 ) space. The interval recursion of the textbook, the pair of the two ends or the best split, gives the same in :math:` Theta( n^3 ) ` time.

  • longestBalancedSubstring(): the longest contiguous balanced substring. A stack keeps the places of the opens not matched yet; when a close matches the top, the substring from the next open still unmatched (or from the last place where the balance broke) to the close is balanced, and it is the longest one ending there: :math:` Theta( n ) ` time and O( n ) space. The two scans of the counts of opens and closes, left to right and right to left, need only O( 1 ) space.

The contracts [see File Contract.h]: the substring found is balanced. The functions are defined in Parentheses.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, chapter 13, https://algoritmicamente.it/materiali/libro/capitoli/cap13.pdf

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • ADS/Contract.h (File Contract.h)

  • ADS/string/impl/Parentheses.tpp

  • cstddef

  • string_view

  • utility

  • vector

Namespaces

Functions