import Mathlib /-! # Substring With Concatenation Of All Words You are given a string s and an array of strings words. All the strings of words are of the same length. A concatenated string is a string that exactly contains all the strings of any permutation of words concatenated. For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated string because it is not the concatenation of any permutation of words. Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order. ## Constraints - 1 <= s.length <= 10^4 - 1 <= words.length <= 5000 - 1 <= words[i].length <= 30 - s and words[i] consist of lowercase English letters. ## Provided examples - `s = "barfoothefoobarman", words = ["foo", "bar"]` → `[0, 9]` - `s = "barfoofoobarthefoobarman", words = ["bar", "foo", "the"]` → `[6, 9, 12]` - `s = "a", words = ["a", "a", "a"]` → `[]` ## Synthesized negative examples - invalid input: `s = "", words = ["a"]` ([structural] a predicate that admits 1 <= s.length <= 10^4. empty string below s length floor) - invalid input: `s = "a", words = ["abcdefghijklmnopqrstuvwxyzabcde"]` ([structural] a predicate that admits 1 <= words[i].length <= 30. word length 31 is one past maximum) - invalid input: `s = "A", words = ["a"]` ([structural] a predicate that admits s and words[i] consist of lowercase English letters.. uppercase in s slips past isalpha checks) - `s = "barfoothefoobarman", words = ["foo", "bar"]` → `[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]` is wrong ([structural] substring condition read as 'contains every word somewhere' instead of 'is a concatenation of all words'. indices 1..8 have substrings containing both words) - `s = "barfoofoobarthefoobarman", words = ["bar", "foo", "the"]` → `[6, 9, 12, 0, 3]` is wrong ([structural] words may be reused, so repeated-word substrings are accepted. extra starts 0 and 3 are built by repeating foo) - `s = "a", words = ["a", "a", "a"]` → `[0]` is wrong ([structural] returns an index without verifying it starts any concatenated substring. any nonempty s yields 0 under this reading) -/ namespace PSubstringWithConcatenationOfAllWords abbrev Input := (String) × (List String) abbrev Output := List Nat /-! ### Specification helpers -/ /-- The substring of `s` starting at `i` of the total concatenation length of `words` is the concatenation of some permutation of `words`. -/ def IsConcatSubstringAt (s : String) (words : List String) (i : Nat) : Prop := ∃ perm : List String, perm.Perm words ∧ (s.toList.drop i).take ((words.map fun w => w.toList.length).sum) = (String.join perm).toList /-! ### Validity predicate (V) -/ /-- Valid input: `s` has 1 to 10^4 lowercase letters, `words` has 1 to 5000 nonempty words of at most 30 lowercase letters each, all of the same length. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length ≤ 10^4 && 1 ≤ input.2.length && input.2.length ≤ 5000 && input.2.all (fun w => 1 ≤ w.length && w.length ≤ 30) && input.1.toList.all (fun c => 'a' ≤ c && c ≤ 'z') && input.2.all (fun w => w.toList.all (fun c => 'a' ≤ c && c ≤ 'z')) && input.2.all (fun w => w.length == (input.2.headD "").length) /-! ### Ideal specification (P_spec) -/ /-- `result` lists, in any order, exactly the starting indices at which a concatenated substring begins: it is a permutation of some finite collection whose members are precisely the indices satisfying `IsConcatSubstringAt`. -/ def findSubstringIndices_spec (input : Input) (result : Output) : Prop := ∃ C : Finset Nat, result.Perm C.toList ∧ ∀ i : Nat, i ∈ C ↔ IsConcatSubstringAt input.1 input.2 i /-! ### Decidable specification (P_check) -/ /-- The total length of the concatenation of all words, as in the specification. -/ def totalConcatLength (words : List String) : Nat := (words.map fun w => w.toList.length).sum /-- Decidable `IsConcatSubstringAt`: some permutation of `words` joins to the substring of `s` at `i`. -/ def concatSubstringAt (s : String) (words : List String) (i : Nat) : Bool := words.permutations.any fun perm => decide ((s.toList.drop i).take (totalConcatLength words) = (String.join perm).toList) /-- The starting indices in `List.range (s.length + 1)` at which a concatenated substring begins. -/ def validStarts (s : String) (words : List String) : List Nat := (List.range (s.length + 1)).filter fun i => concatSubstringAt s words i /-- Executable checker for `findSubstringIndices_spec`: `result` is a permutation of exactly the valid starts. -/ def findSubstringIndices_check (input : Input) (result : Output) : Bool := decide (result.Perm (validStarts input.1 input.2)) theorem root_of_bridges (input : Input) (result : Output) (hm : ∀ i, i ∈ validStarts input.1 input.2 ↔ IsConcatSubstringAt input.1 input.2 i) : findSubstringIndices_check input result ↔ findSubstringIndices_spec input result := by have hn : (validStarts input.1 input.2).Nodup := List.nodup_range.filter _ have hp := List.toFinset_toList hn simp only [findSubstringIndices_check, decide_eq_true_eq, findSubstringIndices_spec] constructor · intro hr refine ⟨(validStarts input.1 input.2).toFinset, hr.trans hp.symm, ?_⟩ intro i simpa only [List.mem_toFinset] using hm i · rintro ⟨C, hr, hc⟩ have heq : C = (validStarts input.1 input.2).toFinset := by ext i simpa only [List.mem_toFinset] using (hc i).trans (hm i).symm rw [heq] at hr exact hr.trans hp theorem concatSubstringAt_iff (s : String) (words : List String) (i : Nat) : concatSubstringAt s words i = true ↔ IsConcatSubstringAt s words i := by simp [concatSubstringAt, IsConcatSubstringAt, totalConcatLength, List.mem_permutations] theorem concat_index_bound (input : Input) (h : isValidInput input = true) (i : Nat) (hi : IsConcatSubstringAt input.1 input.2 i) : i < input.1.length + 1 := by have hv : 1 ≤ input.2.length ∧ ∀ w ∈ input.2, 1 ≤ w.length := by simp only [isValidInput, Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true] at h exact ⟨h.1.1.1.1.1.2, fun w hw => (h.1.1.1.2 w hw).1⟩ have hpos : 0 < totalConcatLength input.2 := by cases he : input.2 with | nil => simp [he] at hv | cons w ws => have hw := hv.2 w (by simp [he]) simp only [totalConcatLength, he, List.map_cons, List.sum_cons, String.length_toList] omega obtain ⟨perm, hp, he⟩ := hi have hlen := congrArg List.length he have hsum := (hp.map (fun w : String => w.toList.length)).sum_eq simp only [List.length_take, List.length_drop, String.toList_join, List.length_flatMap] at hlen change (perm.map (fun w : String => w.toList.length)).sum = totalConcatLength input.2 at hsum rw [hsum] at hlen simp only [String.length_toList] at hlen change min (totalConcatLength input.2) (input.1.length - i) = totalConcatLength input.2 at hlen omega theorem validStarts_mem (input : Input) (h : isValidInput input = true) (i : Nat) : i ∈ validStarts input.1 input.2 ↔ IsConcatSubstringAt input.1 input.2 i := by simp only [validStarts, List.mem_filter, List.mem_range, concatSubstringAt_iff] exact ⟨And.right, fun hi => ⟨concat_index_bound input h i hi, hi⟩⟩ /-- On valid input the checker accepts exactly the specified outputs. -/ theorem findSubstringIndices_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : findSubstringIndices_check input result ↔ findSubstringIndices_spec input result := by exact root_of_bridges input result (validStarts_mem input h) /-! ### Implementation helpers -/ /-- Required occurrence count of each distinct word in `words`. -/ def targetWordCounts (words : List String) : Std.HashMap String Nat := words.foldl (fun m w => m.insert w ((m.get? w).getD 0 + 1)) (∅ : Std.HashMap String Nat) /-- Drop window words from the left while `w` occurs more than `needed` times, over the queue `front` (oldest first) and `back` (newest first). -/ def shrinkExcess (w : String) (needed : Nat) (counts : Std.HashMap String Nat) (left : Nat) (front back : List String) : List String × List String × Std.HashMap String Nat × Nat := if (counts.get? w).getD 0 ≤ needed then (front, back, counts, left) else match front with | u :: fs => shrinkExcess w needed (counts.insert u ((counts.get? u).getD 0 - 1)) (left + 1) fs back | [] => match back with | [] => (front, back, counts, left) | b :: bs => shrinkExcess w needed counts left (b :: bs).reverse [] termination_by 2 * back.length + front.length decreasing_by · simp only [List.length_cons] <;> omega · simp only [List.length_reverse, List.length_cons, List.length_nil] <;> omega /-- All valid window starts in the offset class `offset` modulo `wordLen`, found by sliding a frequency-counted window over word-length chunks. -/ def slidingWindowAtOffset (s : String) (offset wordLen numWords : Nat) (target : Std.HashMap String Nat) : List Nat := let chars := s.toList let numChunks := (chars.length - offset) / wordLen let chunks := (List.range numChunks).map fun k => String.ofList ((chars.drop (offset + k * wordLen)).take wordLen) let init : Nat × Nat × List String × List String × Std.HashMap String Nat × List Nat := (0, 0, [], [], (∅ : Std.HashMap String Nat), []) let result := chunks.foldl (fun st w => let (j, left, front, back, counts, acc) := st match target.get? w with | none => (j + 1, j + 1, [], [], (∅ : Std.HashMap String Nat), acc) | some needed => let (front, back) := if front.isEmpty then (back.reverse, []) else (front, back) let back := w :: back let counts := counts.insert w ((counts.get? w).getD 0 + 1) let (front, back, counts, left) := shrinkExcess w needed counts left front back let acc := if j + 1 - left = numWords then (offset + left * wordLen) :: acc else acc (j + 1, left, front, back, counts, acc)) init let (_, _, _, _, _, starts) := result starts.reverse /-! ### Main algorithm (impl) -/ /-- Sliding window over each residue class modulo the common word length, matching chunk multisets against the word frequency table. -/ def findConcatenatedSubstrings (input : Input) : Output := let s := input.1 match input.2 with | [] => [] | w0 :: _ => let words := input.2 let wordLen := w0.length if wordLen = 0 then [] else if s.toList.length < totalConcatLength words then [] else let target := targetWordCounts words (List.range wordLen).flatMap fun offset => slidingWindowAtOffset s offset wordLen words.length target /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findConcatenatedSubstrings_correct (input : Input) (h : isValidInput input) : findSubstringIndices_spec input (findConcatenatedSubstrings input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ("barfoothefoobarman", ["foo", "bar"]) #guard isValidInput ("barfoofoobarthefoobarman", ["bar", "foo", "the"]) #guard isValidInput ("a", ["a", "a", "a"]) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ("", ["a"])) #guard !(isValidInput ("a", ["abcdefghijklmnopqrstuvwxyzabcde"])) #guard !(isValidInput ("A", ["a"])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard findSubstringIndices_check ("barfoothefoobarman", ["foo", "bar"]) [0, 9] #guard findSubstringIndices_check ("barfoofoobarthefoobarman", ["bar", "foo", "the"]) [6, 9, 12] #guard findSubstringIndices_check ("a", ["a", "a", "a"]) [] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(findSubstringIndices_check ("barfoothefoobarman", ["foo", "bar"]) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]) #guard !(findSubstringIndices_check ("barfoofoobarthefoobarman", ["bar", "foo", "the"]) [6, 9, 12, 0, 3]) #guard !(findSubstringIndices_check ("a", ["a", "a", "a"]) [0]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findConcatenatedSubstrings ("barfoothefoobarman", ["foo", "bar"]) == [0, 9] #guard findConcatenatedSubstrings ("barfoofoobarthefoobarman", ["bar", "foo", "the"]) == [6, 9, 12] #guard findConcatenatedSubstrings ("a", ["a", "a", "a"]) == [] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard findSubstringIndices_check ("barfoothefoobarman", ["foo", "bar"]) (findConcatenatedSubstrings ("barfoothefoobarman", ["foo", "bar"])) #guard findSubstringIndices_check ("barfoofoobarthefoobarman", ["bar", "foo", "the"]) (findConcatenatedSubstrings ("barfoofoobarthefoobarman", ["bar", "foo", "the"])) #guard findSubstringIndices_check ("a", ["a", "a", "a"]) (findConcatenatedSubstrings ("a", ["a", "a", "a"])) end PSubstringWithConcatenationOfAllWords