import Mathlib /-! # Longest Palindromic Substring Given a string s, return the longest palindromic substring in s. ## Constraints - 1 <= s.length <= 1000 - s consist of only digits and English letters. ## Provided examples - `s = "babad"` → `"bab"` - `s = "cbbd"` → `"bb"` - `s = "a"` → `"a"` ## Synthesized negative examples - invalid input: `s = ""` ([structural] a predicate that admits 1 <= s.length <= 1000. empty string below stated minimum length) - invalid input: `s = " "` ([structural] a predicate that admits s consist of only digits and English letters.. whitespace outside allowed alphabet; a predicate that trims before checking accepts it) - invalid input: `s = "é"` ([structural] a predicate that admits s consist of only digits and English letters.. Unicode letter outside English; a predicate using isalpha accepts it) - `s = "babad"` → `"a"` is wrong ([structural] maximality stated as achievability alone. a is a palindrome substring but not longest) - `s = "cbbd"` → `"cb"` is wrong ([structural] the output is not required to be a palindrome. substring of length 2, same as longest palindrome length, but not palindromic) - `s = "a"` → `"aa"` is wrong ([structural] specification loses the requirement that the answer be a substring of s. longer than any palindromic substring of s) -/ namespace PLongestPalindromicSubstring abbrev Input := String abbrev Output := String /-! ### Specification helpers -/ /-- `p` occurs as a contiguous substring of `s` and reads the same forwards and backwards. -/ def IsPalindromicSubstring (s p : String) : Prop := p.toList <:+: s.toList ∧ p.toList.Palindrome /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 1000 characters, each a digit or an English letter. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 1000 && input.toList.all (fun c => ('0' ≤ c && c ≤ '9') || ('a' ≤ c && c ≤ 'z') || ('A' ≤ c && c ≤ 'Z')) /-! ### Ideal specification (P_spec) -/ /-- `result` is a palindromic substring of `input`, and no palindromic substring is longer. -/ def longestPalindrome_spec (input : Input) (result : Output) : Prop := IsPalindromicSubstring input result ∧ ∀ p : String, IsPalindromicSubstring input p → p.length ≤ result.length /-! ### Decidable specification (P_check) -/ /-- The contiguous slice of `s` from character index `start` up to `stop`. -/ def sliceString (s : String) (start stop : Nat) : String := String.ofList ((s.toList.drop start).take (stop - start)) /-- Boolean check that `needle` occurs as a contiguous block inside `hay`. -/ def isInfixChars (needle hay : List Char) : Bool := needle.length ≤ hay.length && (List.range (hay.length - needle.length + 1)).any (fun start => (hay.drop start).take needle.length == needle) /-- Boolean check that `p` is a contiguous palindromic substring of `s`. -/ def isPalindromicSubstringB (s p : String) : Bool := isInfixChars p.toList s.toList && decide p.toList.Palindrome /-- Executable checker for `longestPalindrome_spec` over start and end indices. -/ def longestPalindrome_check (input : Input) (result : Output) : Bool := isPalindromicSubstringB input result && (List.finRange (input.length + 1)).all (fun start => (List.finRange (input.length + 1)).all (fun stop => !(start.val ≤ stop.val) || !(decide (sliceString input start.val stop.val).toList.Palindrome) || (sliceString input start.val stop.val).length ≤ result.length)) theorem root_of_bridges (hb : ∀ (p s : List Char), isInfixChars p s = true ↔ p <:+: s) (hs : ∀ (s : String) (i j : Nat), (sliceString s i j).toList <:+: s.toList) (he : ∀ (s p : String), p.toList <:+: s.toList → ∃ i j : Fin (s.length + 1), i.val ≤ j.val ∧ sliceString s i.val j.val = p) (input result : String) : longestPalindrome_check input result ↔ longestPalindrome_spec input result := by simp only [longestPalindrome_check, isPalindromicSubstringB, Bool.and_eq_true, hb, decide_eq_true_eq, List.all_eq_true, List.mem_finRange, forall_true_left, Bool.or_eq_true, Bool.not_eq_true', decide_eq_false_iff_not, longestPalindrome_spec, IsPalindromicSubstring] constructor · rintro ⟨hres, hall⟩ refine ⟨hres, ?_⟩ intro p hp obtain ⟨i, j, hij, eq⟩ := he input p hp.1 have hh := hall i j rw [eq] at hh rcases hh with (hn | hn) | hn · exact False.elim (hn hij) · exact False.elim (hn hp.2) · exact hn · rintro ⟨hres, hmax⟩ refine ⟨hres, ?_⟩ intro i j by_cases hij : i.val ≤ j.val · by_cases hp : (sliceString input i.val j.val).toList.Palindrome · exact Or.inr (hmax _ ⟨hs input _ _, hp⟩) · exact Or.inl (Or.inr hp) · exact Or.inl (Or.inl hij) theorem slice_infix_bridge (s : String) (i j : Nat) : (sliceString s i j).toList <:+: s.toList := by simp only [sliceString, String.toList_ofList] exact List.infix_iff_prefix_suffix.mpr ⟨s.toList.drop i, List.take_prefix _ _, List.drop_suffix _ _⟩ theorem infix_bool_bridge (p s : List Char) : isInfixChars p s = true ↔ p <:+: s := by simp only [isInfixChars, Bool.and_eq_true, decide_eq_true_eq, List.any_eq_true, List.mem_range, beq_iff_eq] constructor · rintro ⟨hlen, i, hi, heq⟩ rw [← heq] exact List.infix_iff_prefix_suffix.mpr ⟨s.drop i, List.take_prefix _ _, List.drop_suffix _ _⟩ · rintro ⟨a, b, rfl⟩ refine ⟨by simp only [List.length_append]; omega, a.length, ?_, ?_⟩ · simp only [List.length_append] omega · simp [List.append_assoc] theorem infix_slice_bridge (s p : String) (h : p.toList <:+: s.toList) : ∃ i j : Fin (s.length + 1), i.val ≤ j.val ∧ sliceString s i.val j.val = p := by obtain ⟨a, b, heq⟩ := h have hlen := congrArg List.length heq simp only [List.length_append, String.length_toList] at hlen refine ⟨⟨a.length, by omega⟩, ⟨a.length + p.length, by omega⟩, by simp, ?_⟩ apply String.toList_inj.mp simp only [sliceString, String.toList_ofList] rw [← heq] simp [List.append_assoc, ← String.length_toList] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem longestPalindrome_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : longestPalindrome_check input result ↔ longestPalindrome_spec input result := by exact root_of_bridges infix_bool_bridge slice_infix_bridge infix_slice_bridge input result /-! ### Implementation helpers -/ /-- Expands outward from boundaries `l` and `r` while both characters match, returning the inclusive boundaries of the maximal palindrome centered there. -/ def expandAt (cs : Array Char) (l r : Nat) : Nat × Nat := if hl : l < cs.size then if hr : r < cs.size then if cs[l] = cs[r] then if hb : l = 0 ∨ r + 1 = cs.size then (l, r) else expandAt cs (l - 1) (r + 1) else (l + 1, r - 1) else (l + 1, r - 1) else (l + 1, r - 1) termination_by min l (cs.size - 1 - r) decreasing_by decreasing_tactic /-- Scans every odd and even center, keeping the inclusive boundaries of the longest palindrome found. -/ def bestInterval (cs : Array Char) : Nat × Nat := (List.range cs.size).foldl (fun acc i => let acc := let (l, r) := expandAt cs i i if acc.2 - acc.1 < r - l then (l, r) else acc let (l, r) := expandAt cs i (i + 1) if acc.2 - acc.1 < r - l then (l, r) else acc) (0, 0) /-! ### Main algorithm (impl) -/ /-- Longest palindromic substring by expanding around each of the 2n−1 centers and slicing out the best interval. -/ def longestPalindromicSubstring (input : Input) : Output := let cs := input.toList.toArray let (l, r) := bestInterval cs sliceString input l (r + 1) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem longestPalindromicSubstring_correct (input : Input) (h : isValidInput input) : longestPalindrome_spec input (longestPalindromicSubstring input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput "babad" #guard isValidInput "cbbd" #guard isValidInput "a" /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput "") #guard !(isValidInput " ") #guard !(isValidInput "é") /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard longestPalindrome_check "babad" "bab" #guard longestPalindrome_check "cbbd" "bb" #guard longestPalindrome_check "a" "a" /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(longestPalindrome_check "babad" "a") #guard !(longestPalindrome_check "cbbd" "cb") #guard !(longestPalindrome_check "a" "aa") /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard longestPalindromicSubstring "babad" == "bab" #guard longestPalindromicSubstring "cbbd" == "bb" #guard longestPalindromicSubstring "a" == "a" /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard longestPalindrome_check "babad" (longestPalindromicSubstring "babad") #guard longestPalindrome_check "cbbd" (longestPalindromicSubstring "cbbd") #guard longestPalindrome_check "a" (longestPalindromicSubstring "a") end PLongestPalindromicSubstring