import Mathlib /-! # Longest Valid Parentheses Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring. ## Constraints - 0 <= s.length <= 3 * 10^4 - s[i] is '(', or ')'. ## Provided examples - `s = "(()"` → `2` - `s = ")()())"` → `4` - `s = ""` → `0` ## Synthesized negative examples - invalid input: `s = "["` ([structural] a predicate that admits s[i] is '(', or ')'.. predicate written for generic brackets accepts a single bracket) - invalid input: `s = " "` ([structural] a predicate that admits s[i] is '(', or ')'.. whitespace slips past predicates that only reject letters) - invalid input: `s = "a"` ([structural] a predicate that admits s[i] is '(', or ')'.. obvious character outside the stated alphabet) - `s = "(()"` → `0` is wrong ([structural] maximality stated as achievability alone. 0 is the empty valid substring, but not longest.) - `s = ")()())"` → `2` is wrong ([structural] longest stated as existence rather than maximum. 2 is a valid substring length but not the longest) - `s = ""` → `1` is wrong ([structural] No requirement that the returned length be realized by a valid substring.. 1 exceeds 0 but no substring has length 1.) -/ namespace PLongestValidParentheses abbrev Input := String abbrev Output := Nat /-! ### Specification helpers -/ /-- Map a parenthesis character to a Dyck step, '(' as up and anything else as down. -/ def charToStep (c : Char) : DyckStep := if c = '(' then DyckStep.U else DyckStep.D /-- The block of `length` characters of `s` starting at offset `start` lies inside `s` and is a well-formed parentheses string. -/ def IsValidSubstring (s : String) (start length : Nat) : Prop := start + length ≤ s.length ∧ ∃ w : DyckWord, w.toList = ((s.toList.drop start).take length).map charToStep /-! ### Validity predicate (V) -/ /-- Valid input: a string of at most 30000 characters, each '(' or ')'. -/ def isValidInput (input : Input) : Bool := input.length ≤ 30000 && input.toList.all (fun c => c == '(' || c == ')') /-! ### Ideal specification (P_spec) -/ /-- `result` is the greatest length attained by a well-formed parentheses substring of `input`. -/ def longestValidParentheses_spec (input : Input) (result : Output) : Prop := IsGreatest {n : Nat | ∃ start : Nat, IsValidSubstring input start n} result /-! ### Decidable specification (P_check) -/ /-- The mapped step list has the two Dyck word properties: equal counts and no prefix with more downs than ups. -/ def isDyckList (l : List DyckStep) : Bool := (l.count DyckStep.U == l.count DyckStep.D) && (List.range (l.length + 1)).all (fun i => (l.take i).count DyckStep.D ≤ (l.take i).count DyckStep.U) /-- Decidable form of `IsValidSubstring`: the block lies inside `s` and its step list is a Dyck word. -/ def validSubstringCheck (s : String) (start length : Nat) : Bool := (start + length ≤ s.length) && isDyckList (((s.toList.drop start).take length).map charToStep) /-- Executable checker for `longestValidParentheses_spec` with `start` and the length index truncated to `input.length`. -/ def longestValidParentheses_check (input : Input) (result : Output) : Bool := (List.range (input.length + 1)).any (fun start => validSubstringCheck input start result) && (List.range (input.length + 1)).all (fun n => (List.range (input.length + 1)).all (fun start => !validSubstringCheck input start n || n ≤ result)) theorem dyck_bridge (l : List DyckStep) : isDyckList l = true ↔ ∃ w : DyckWord, w.toList = l := by constructor · intro h simp only [isDyckList, Bool.and_eq_true, beq_iff_eq, List.all_eq_true, List.mem_range, decide_eq_true_eq] at h refine ⟨⟨l, h.1, ?_⟩, rfl⟩ intro i by_cases hi : i < l.length + 1 · exact h.2 i hi · rw [List.take_of_length_le (by omega), h.1] · rintro ⟨w, rfl⟩ simp only [isDyckList, Bool.and_eq_true, beq_iff_eq, List.all_eq_true, List.mem_range, decide_eq_true_eq] exact ⟨w.count_U_eq_count_D, fun i _ => w.count_D_le_count_U i⟩ theorem validSubstring_bridge (s : String) (start length : Nat) : validSubstringCheck s start length = true ↔ IsValidSubstring s start length := by simp only [validSubstringCheck, IsValidSubstring, Bool.and_eq_true, decide_eq_true_eq, dyck_bridge] theorem bounded_bool_greatest (P : Nat → Nat → Prop) (q : Nat → Nat → Bool) (N result : Nat) (bridge : ∀ start length, q start length = true ↔ P start length) (bound : ∀ start length, P start length → start ≤ N ∧ length ≤ N) : ((List.range (N + 1)).any (fun start => q start result) && (List.range (N + 1)).all (fun n => (List.range (N + 1)).all (fun start => !q start n || n ≤ result))) ↔ IsGreatest {n : Nat | ∃ start : Nat, P start n} result := by simp [bridge, IsGreatest, mem_upperBounds] grind only [] theorem longest_valid_parentheses_root_of_bridge (bridge : ∀ s start length, validSubstringCheck s start length = true ↔ IsValidSubstring s start length) (input : Input) (result : Output) : longestValidParentheses_check input result ↔ longestValidParentheses_spec input result := by unfold longestValidParentheses_check longestValidParentheses_spec apply bounded_bool_greatest · exact fun start length => bridge input start length · intro start length hs unfold IsValidSubstring at hs omega /-- On valid input the checker accepts exactly the specified outputs. -/ theorem longestValidParentheses_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : longestValidParentheses_check input result ↔ longestValidParentheses_spec input result := by exact longest_valid_parentheses_root_of_bridge validSubstring_bridge input result /-! ### Implementation helpers -/ /-- One-pass scan carrying the current index, the stack of unmatched '(' indices, the segment base, and the best length seen so far. -/ def scan (cs : List Char) (i : Nat) (stack : List Nat) (base best : Nat) : Nat := match cs with | [] => best | c :: rest => match charToStep c with | DyckStep.U => scan rest (i + 1) (i :: stack) base best | DyckStep.D => match stack with | [] => scan rest (i + 1) [] (i + 1) best | _ :: stk => match stk with | [] => scan rest (i + 1) stk base (Nat.max best (i + 1 - base)) | t :: _ => scan rest (i + 1) stk base (Nat.max best (i - t)) /-! ### Main algorithm (impl) -/ /-- Length of the longest valid parentheses substring by a one-pass stack scan over the characters. -/ def longestValidParenthesesSubstring (input : Input) : Output := scan input.toList 0 [] 0 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem longestValidParenthesesSubstring_correct (input : Input) (h : isValidInput input) : longestValidParentheses_spec input (longestValidParenthesesSubstring input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput "(()" #guard isValidInput ")()())" #guard isValidInput "" /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput "[") #guard !(isValidInput " ") #guard !(isValidInput "a") /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard longestValidParentheses_check "(()" 2 #guard longestValidParentheses_check ")()())" 4 #guard longestValidParentheses_check "" 0 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(longestValidParentheses_check "(()" 0) #guard !(longestValidParentheses_check ")()())" 2) #guard !(longestValidParentheses_check "" 1) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard longestValidParenthesesSubstring "(()" == 2 #guard longestValidParenthesesSubstring ")()())" == 4 #guard longestValidParenthesesSubstring "" == 0 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard longestValidParentheses_check "(()" (longestValidParenthesesSubstring "(()") #guard longestValidParentheses_check ")()())" (longestValidParenthesesSubstring ")()())") #guard longestValidParentheses_check "" (longestValidParenthesesSubstring "") end PLongestValidParentheses