import Mathlib /-! # Longest Substring Without Repeating Characters Given a string s, find the length of the longest substring without repeating characters. ## Constraints - 0 <= s.length <= 5 * 10^4 - s consists of English letters, digits, symbols and spaces. ## Provided examples - `s = "abcabcbb"` → `3` - `s = "bbbbb"` → `1` - `s = "pwwkew"` → `3` ## Synthesized negative examples - invalid input: `s = "\u0001"` ([structural] a predicate that admits s consists of English letters, digits, symbols and spaces.. ASCII control character; ASCII-range predicates accept it) - invalid input: `s = "\t"` ([structural] a predicate that admits s consists of English letters, digits, symbols and spaces.. tab is whitespace, not a space; string.printable predicates accept it) - invalid input: `s = "中"` ([structural] a predicate that admits s consists of English letters, digits, symbols and spaces.. CJK ideograph is not an English letter; printable-only predicates accept it) - `s = "abcabcbb"` → `4` is wrong ([structural] no substring is required to attain the answer. 4 exceeds any valid substring length) - `s = "bbbbb"` → `0` is wrong ([structural] no maximality clause is stated, so zero is accepted. empty substring satisfies if only existence is required) - `s = "pwwkew"` → `2` is wrong ([structural] maximality stated as achievability alone. 2 is a real substring length but not the longest) -/ namespace PLongestSubstringWithoutRepeatingCharacters abbrev Input := String abbrev Output := Nat /-! ### Specification helpers -/ /-- The contiguous block of `s` starting at `start` with length `len` lies within `s` and has all characters distinct. -/ def IsSubstringWithoutRepeatingCharacters (s : String) (start len : Nat) : Prop := start + len ≤ s.length ∧ ((s.toList.drop start).take len).Nodup /-! ### Validity predicate (V) -/ /-- Valid input: a string of at most 50000 printable ASCII characters (letters, digits, symbols, spaces). -/ def isValidInput (input : Input) : Bool := input.length ≤ 50000 && input.toList.all (fun c => ' ' ≤ c && c ≤ '~') /-! ### Ideal specification (P_spec) -/ /-- `result` is the greatest length attained by any contiguous substring of `input` without repeating characters. -/ def lengthOfLongestSubstring_spec (input : Input) (result : Output) : Prop := IsGreatest {len | ∃ start : Nat, IsSubstringWithoutRepeatingCharacters input start len} result /-! ### Decidable specification (P_check) -/ /-- Decidability of `List.Nodup` on character lists, so that `decide` can evaluate the bounded quantifiers in the checker below. -/ instance decNodupChars : (l : List Char) → Decidable l.Nodup | [] => isTrue List.nodup_nil | c :: cs => match decNodupChars cs with | isTrue hcs => if h : c ∈ cs then isFalse (fun hn => (List.nodup_cons.mp hn).1 h) else isTrue (List.nodup_cons.mpr ⟨h, hcs⟩) | isFalse hcs => isFalse (fun hn => hcs (List.nodup_cons.mp hn).2) /-- Decidability of `IsSubstringWithoutRepeatingCharacters` itself: type class resolution does not unfold the helper definition on its own, so the instance is registered directly and delegates to the decidable bounds check and the `List.Nodup` instance above. -/ instance decIsSubstringWithoutRepeatingCharacters (input : Input) (start len : Nat) : Decidable (IsSubstringWithoutRepeatingCharacters input start len) := inferInstanceAs (Decidable (start + len ≤ input.length ∧ ((input.toList.drop start).take len).Nodup)) /-- Executable checker for `lengthOfLongestSubstring_spec`: `result` is attained by some valid substring and bounds every valid substring's length, with start and length truncated to `input.length` since validity forces `start + len ≤ input.length`. -/ def lengthOfLongestSubstring_check (input : Input) (result : Output) : Bool := (List.range (input.length + 1)).any (fun start => decide (IsSubstringWithoutRepeatingCharacters input start result)) && (List.range (input.length + 1)).all (fun len => (List.range (input.length + 1)).all (fun start => !decide (IsSubstringWithoutRepeatingCharacters input start len) || decide (len ≤ result))) theorem substr_start_le {input : Input} {start len : Nat} (hs : IsSubstringWithoutRepeatingCharacters input start len) : start ≤ input.length ∧ len ≤ input.length := by have h1 : start + len ≤ input.length := hs.1 omega theorem anyClause_iff (input : Input) (result : Output) : ((List.range (input.length + 1)).any (fun start => decide (IsSubstringWithoutRepeatingCharacters input start result))) = true ↔ ∃ start : Nat, IsSubstringWithoutRepeatingCharacters input start result := by simp only [List.any_eq_true, List.mem_range, decide_eq_true_eq] constructor · rintro ⟨start, -, hs⟩ exact ⟨start, hs⟩ · rintro ⟨start, hs⟩ have hb : start ≤ input.length ∧ result ≤ input.length := substr_start_le hs exact ⟨start, by omega, hs⟩ theorem allClause_iff (input : Input) (result : Output) : ((List.range (input.length + 1)).all (fun len => (List.range (input.length + 1)).all (fun start => !decide (IsSubstringWithoutRepeatingCharacters input start len) || decide (len ≤ result)))) = true ↔ ∀ len : Nat, (∃ start : Nat, IsSubstringWithoutRepeatingCharacters input start len) → len ≤ result := by constructor · intro hall len hlen obtain ⟨start, hs⟩ := hlen have hb : start ≤ input.length ∧ len ≤ input.length := substr_start_le hs have h1 : ((List.range (input.length + 1)).all (fun start => !decide (IsSubstringWithoutRepeatingCharacters input start len) || decide (len ≤ result))) = true := List.all_eq_true.mp hall len (List.mem_range.mpr (by omega)) have h2 : (!decide (IsSubstringWithoutRepeatingCharacters input start len) || decide (len ≤ result)) = true := List.all_eq_true.mp h1 start (List.mem_range.mpr (by omega)) rcases Bool.or_eq_true_iff.mp h2 with hf | hle · exact absurd hs (by simpa using hf) · exact of_decide_eq_true hle · intro hall refine List.all_eq_true.mpr ?_ intro len _ show ((List.range (input.length + 1)).all (fun start => !decide (IsSubstringWithoutRepeatingCharacters input start len) || decide (len ≤ result))) = true refine List.all_eq_true.mpr ?_ intro start _ show (!decide (IsSubstringWithoutRepeatingCharacters input start len) || decide (len ≤ result)) = true refine Bool.or_eq_true_iff.mpr ?_ by_cases hs : IsSubstringWithoutRepeatingCharacters input start len · exact Or.inr (decide_eq_true (hall len ⟨start, hs⟩)) · exact Or.inl (by simpa using hs) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem lengthOfLongestSubstring_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : lengthOfLongestSubstring_check input result ↔ lengthOfLongestSubstring_spec input result := by constructor · intro hc have hc' : ((List.range (input.length + 1)).any (fun start => decide (IsSubstringWithoutRepeatingCharacters input start result)) && (List.range (input.length + 1)).all (fun len => (List.range (input.length + 1)).all (fun start => !decide (IsSubstringWithoutRepeatingCharacters input start len) || decide (len ≤ result)))) = true := hc obtain ⟨h1, h2⟩ := Bool.and_eq_true_iff.mp hc' have h1' : ∃ start : Nat, IsSubstringWithoutRepeatingCharacters input start result := (anyClause_iff input result).mp h1 have h2' : ∀ len : Nat, (∃ start : Nat, IsSubstringWithoutRepeatingCharacters input start len) → len ≤ result := (allClause_iff input result).mp h2 refine ⟨h1', ?_⟩ intro n hn exact h2' n hn · intro hspec obtain ⟨hmem, hub⟩ := hspec have h1' : ∃ start : Nat, IsSubstringWithoutRepeatingCharacters input start result := hmem have h2' : ∀ len : Nat, (∃ start : Nat, IsSubstringWithoutRepeatingCharacters input start len) → len ≤ result := fun len hlen => hub hlen show ((List.range (input.length + 1)).any (fun start => decide (IsSubstringWithoutRepeatingCharacters input start result)) && (List.range (input.length + 1)).all (fun len => (List.range (input.length + 1)).all (fun start => !decide (IsSubstringWithoutRepeatingCharacters input start len) || decide (len ≤ result)))) = true exact Bool.and_eq_true_iff.mpr ⟨(anyClause_iff input result).mpr h1', (allClause_iff input result).mpr h2'⟩ /-! ### Implementation helpers -/ /-- The index 0..94 of a printable ASCII character in the fixed-size last-occurrence table. -/ def asciiIndex (c : Char) : Nat := c.toNat - ' '.toNat /-- Tail-recursive sliding-window scan over the remaining characters, carrying the current index, the window's left boundary, the last-occurrence table (storing positions plus one, 0 meaning unseen), and the best length found. -/ def longestSubstringAux (cs : List Char) (idx left : Nat) (last : Array Nat) (best : Nat) : Nat := match cs with | [] => best | c :: rest => let code := asciiIndex c let prev := last[code]! let left' := if prev > left then prev else left let last' := last.set! code (idx + 1) let best' := Nat.max best (idx + 1 - left') longestSubstringAux rest (idx + 1) left' last' best' /-! ### Main algorithm (impl) -/ /-- Longest substring without repeating characters by a single sliding-window pass with a last-occurrence table. -/ def lengthOfLongestSubstringImpl (input : Input) : Output := longestSubstringAux input.toList 0 0 (Array.replicate 95 0) 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem lengthOfLongestSubstringImpl_correct (input : Input) (h : isValidInput input) : lengthOfLongestSubstring_spec input (lengthOfLongestSubstringImpl input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput "abcabcbb" #guard isValidInput "bbbbb" #guard isValidInput "pwwkew" /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput "\u0001") #guard !(isValidInput "\t") #guard !(isValidInput "中") /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard lengthOfLongestSubstring_check "abcabcbb" 3 #guard lengthOfLongestSubstring_check "bbbbb" 1 #guard lengthOfLongestSubstring_check "pwwkew" 3 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(lengthOfLongestSubstring_check "abcabcbb" 4) #guard !(lengthOfLongestSubstring_check "bbbbb" 0) #guard !(lengthOfLongestSubstring_check "pwwkew" 2) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard lengthOfLongestSubstringImpl "abcabcbb" == 3 #guard lengthOfLongestSubstringImpl "bbbbb" == 1 #guard lengthOfLongestSubstringImpl "pwwkew" == 3 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard lengthOfLongestSubstring_check "abcabcbb" (lengthOfLongestSubstringImpl "abcabcbb") #guard lengthOfLongestSubstring_check "bbbbb" (lengthOfLongestSubstringImpl "bbbbb") #guard lengthOfLongestSubstring_check "pwwkew" (lengthOfLongestSubstringImpl "pwwkew") end PLongestSubstringWithoutRepeatingCharacters