import Mathlib /-! # Minimum Window Substring Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "". The testcases will be generated such that the answer is unique. ## Constraints - m == s.length - n == t.length - 1 <= m, n <= 10^5 - s and t consist of uppercase and lowercase English letters. ## Provided examples - `s = "ADOBECODEBANC", t = "ABC"` → `"BANC"` - `s = "a", t = "a"` → `"a"` - `s = "a", t = "aa"` → `""` ## Synthesized negative examples - invalid input: `s = "", t = "a"` ([structural] a predicate that admits 1 <= m, n <= 10^5. empty s; m=0 below the stated minimum) - invalid input: `s = "0", t = "a"` ([structural] a predicate that admits s and t consist of uppercase and lowercase English letters.. digit in s; a predicate accepting any character passes) - invalid input: `s = "a", t = ""` ([structural] a predicate that admits 1 <= m, n <= 10^5. empty t; n=0 below the stated minimum) - `s = "ADOBECODEBANC", t = "ABC"` → `"ADOBEC"` is wrong ([structural] minimality stated as achievability alone. contains A,B,C but is not shortest) - `s = "a", t = "a"` → `""` is wrong ([structural] nothing requires the result to contain every character of t. empty string is accepted if containment is not required) - `s = "a", t = "aa"` → `"aa"` is wrong ([structural] the output is not required to be a substring of s. minimum string containing t, ignoring substring) -/ namespace PMinimumWindowSubstring abbrev Input := (String) × (String) abbrev Output := String /-! ### Specification helpers -/ /-- `w` is a contiguous substring of `s` in which every character occurs at least as many times as in `t`. -/ def IsWindow (s t w : String) : Prop := w.toList <:+: s.toList ∧ ∀ c : Char, t.toList.count c ≤ w.toList.count c /-! ### Validity predicate (V) -/ /-- Valid input: both strings have length between 1 and 100000 and consist only of English letters. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length ≤ 100000 && 1 ≤ input.2.length && input.2.length ≤ 100000 && input.1.toList.all (fun c => 'a' ≤ c && c ≤ 'z' || 'A' ≤ c && c ≤ 'Z') && input.2.toList.all (fun c => 'a' ≤ c && c ≤ 'z' || 'A' ≤ c && c ≤ 'Z') /-! ### Ideal specification (P_spec) -/ /-- `result` is a covering window of minimum length, or the empty string when no covering window exists. -/ def minWindowSubstring_spec (input : Input) (result : Output) : Prop := (IsWindow input.1 input.2 result ∨ (¬∃ w : String, IsWindow input.1 input.2 w) ∧ result = "") ∧ ∀ w : String, IsWindow input.1 input.2 w → result.length ≤ w.length /-! ### Decidable specification (P_check) -/ /-- Every contiguous substring of `s`, generated by start index and length. -/ def windowsOf (s : String) : List String := let cs := s.toList (List.range (cs.length + 1)).flatMap fun start => (List.range (cs.length - start + 1)).map fun len => String.ofList ((cs.drop start).take len) /-- Whether `w` contains each character of `t` at least as many times as `t` does. -/ def covers (t w : String) : Bool := t.toList.all fun c => decide (List.count c t.toList ≤ List.count c w.toList) /-- Executable checker for `minWindowSubstring_spec` over the finite windows of `s`. -/ def minWindowSubstring_check (input : Input) (result : Output) : Bool := let s := input.1 let t := input.2 let ws := windowsOf s ((ws.any (fun w => w == result) && covers t result) || (ws.all (fun w => !covers t w) && result == "")) && ws.all (fun w => !covers t w || decide (result.length ≤ w.length)) theorem mw_mem_windowsOf (s w : String) : w ∈ windowsOf s ↔ w.toList <:+: s.toList := by simp only [windowsOf, List.mem_flatMap, List.mem_range, List.mem_map] constructor · rintro ⟨st, -, len, -, rfl⟩ rw [String.toList_ofList] exact (List.take_prefix len _).isInfix.trans (List.drop_suffix st _).isInfix · rintro ⟨a, b, hab⟩ refine ⟨a.length, ?_, w.toList.length, ?_, ?_⟩ · rw [← hab]; simp · rw [← hab]; simp · rw [← hab]; simp theorem mw_covers_iff (t w : String) : covers t w = true ↔ ∀ c : Char, t.toList.count c ≤ w.toList.count c := by simp only [covers, List.all_eq_true, decide_eq_true_eq] constructor · intro hall c by_cases hc : c ∈ t.toList · exact hall c hc · rw [List.count_eq_zero_of_not_mem hc]; exact Nat.zero_le _ · intro hall c _ exact hall c theorem mw_isWindow_iff (s t w : String) : IsWindow s t w ↔ w ∈ windowsOf s ∧ covers t w = true := by rw [mw_mem_windowsOf, mw_covers_iff]; rfl /-- On valid input the checker accepts exactly the specified outputs. -/ theorem minWindowSubstring_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : minWindowSubstring_check input result ↔ minWindowSubstring_spec input result := by obtain ⟨s, t⟩ := input simp only [minWindowSubstring_check, minWindowSubstring_spec, Bool.and_eq_true, Bool.or_eq_true, List.any_eq_true, List.all_eq_true, beq_iff_eq, Bool.not_eq_true', decide_eq_true_eq, mw_isWindow_iff] grind /-! ### Implementation helpers -/ /-- Set index `i` of a natural-number array to `v`, padding with zeros when `i` is past the end. -/ def setNatD (a : Array Nat) (i : Nat) (v : Nat) : Array Nat := if h : i < a.size then a.set i v h else (a ++ Array.replicate (i - a.size) 0).push v /-- One pass over `t` building the required-frequency array and the number of distinct required characters. -/ def requirementCounts (t : String) : Array Nat × Nat := t.toList.foldl (fun p c => let old := p.1.getD c.toNat 0 (setNatD p.1 c.toNat (old + 1), if decide (c.toNat < 128) && old == 0 then p.2 + 1 else p.2)) (Array.replicate 128 0, 0) /-- One character entering or leaving the window updates the window frequencies and the satisfied-character count. -/ def stepWindow (need win : Array Nat) (formed : Nat) (c : Char) (enter : Bool) : Array Nat × Nat := let req := need.getD c.toNat 0 let cur := win.getD c.toNat 0 if enter then (setNatD win c.toNat (cur + 1), if req != 0 && cur + 1 == req then formed + 1 else formed) else (setNatD win c.toNat (cur - 1), if req != 0 && cur == req then formed - 1 else formed) /-- Keeps the shorter of the recorded best window and the candidate `(start, len)`. -/ def recordBest (best : Nat × Nat) (start len : Nat) : Nat × Nat := if best.2 == 0 || decide (len < best.2) then (start, len) else best /-! ### Main algorithm (impl) -/ /-- Minimum covering window by a two-pointer sliding window over the character array of `s` with O(1) frequency updates. -/ def findMinWindowSubstring (input : Input) : Output := let cs := input.1.toList.toArray let n := cs.size let (need, required) := requirementCounts input.2 let rec shrink (win : Array Nat) (formed left right : Nat) (best : Nat × Nat) : Array Nat × Nat × Nat × (Nat × Nat) := if h : formed = required ∧ left < right + 1 then let best' := recordBest best left (right + 1 - left) let (win', formed') := stepWindow need win formed cs[left]! false shrink win' formed' (left + 1) right best' else (win, formed, left, best) termination_by right + 1 - left decreasing_by omega let step (st : Array Nat × Nat × Nat × (Nat × Nat)) (right : Nat) : Array Nat × Nat × Nat × (Nat × Nat) := let (win, formed, left, best) := st let (win', formed') := stepWindow need win formed cs[right]! true shrink win' formed' left right best let (_, _, _, (start, len)) := (List.range n).foldl step (Array.replicate 128 0, 0, 0, (0, 0)) String.ofList ((cs.toList.drop start).take len) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findMinWindowSubstring_correct (input : Input) (h : isValidInput input) : minWindowSubstring_spec input (findMinWindowSubstring input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ("ADOBECODEBANC", "ABC") #guard isValidInput ("a", "a") #guard isValidInput ("a", "aa") /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ("", "a")) #guard !(isValidInput ("0", "a")) #guard !(isValidInput ("a", "")) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard minWindowSubstring_check ("ADOBECODEBANC", "ABC") "BANC" #guard minWindowSubstring_check ("a", "a") "a" #guard minWindowSubstring_check ("a", "aa") "" /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(minWindowSubstring_check ("ADOBECODEBANC", "ABC") "ADOBEC") #guard !(minWindowSubstring_check ("a", "a") "") #guard !(minWindowSubstring_check ("a", "aa") "aa") /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findMinWindowSubstring ("ADOBECODEBANC", "ABC") == "BANC" #guard findMinWindowSubstring ("a", "a") == "a" #guard findMinWindowSubstring ("a", "aa") == "" /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard minWindowSubstring_check ("ADOBECODEBANC", "ABC") (findMinWindowSubstring ("ADOBECODEBANC", "ABC")) #guard minWindowSubstring_check ("a", "a") (findMinWindowSubstring ("a", "a")) #guard minWindowSubstring_check ("a", "aa") (findMinWindowSubstring ("a", "aa")) end PMinimumWindowSubstring