import Mathlib /-! # Distinct Subsequences Given two strings s and t, return the number of distinct subsequences of s which equals t. The test cases are generated so that the answer fits on a 32-bit signed integer. ## Constraints - 1 <= s.length, t.length <= 1000 - s and t consist of English letters. ## Provided examples - `s = "rabbbit", t = "rabbit"` → `3` - `s = "babgbag", t = "bag"` → `5` - `s = "abc", t = "abcd"` → `0` ## Synthesized negative examples - invalid input: `s = "a1b", t = "ab"` ([structural] a predicate that admits s and t consist of English letters.. s contains a digit; defeats a predicate that validates only t.) - invalid input: `s = "ab", t = "a1b"` ([structural] a predicate that admits s and t consist of English letters.. t contains a digit; defeats a predicate that validates only s.) - invalid input: `s = "a b", t = "ab"` ([structural] a predicate that admits s and t consist of English letters.. s contains an interior space, which is not an English letter.) - `s = "rabbbit", t = "rabbit"` → `2` is wrong ([structural] The count is computed with an off-by-one error.. One way is omitted, so answer is one less.) - `s = "babgbag", t = "bag"` → `4` is wrong ([structural] unattainable doesn't fit; maximality missing, any achievable count accepted. four real selections exist but three are omitted) - `s = "abc", t = "abcd"` → `8` is wrong ([structural] drops the requirement that subsequences equal t. this is 2^3, the total number of subsequences) -/ namespace PDistinctSubsequences abbrev Input := (String) × (String) abbrev Output := Int /-! ### Specification helpers -/ /-- `idx` is a strictly increasing list of positions in `s` whose characters spell `t`. -/ def IsSubsequenceIndices (s t : String) (idx : List ℕ) : Prop := idx.Pairwise (· < ·) ∧ idx.map (fun i => s.toList[i]?) = t.toList.map some /-! ### Validity predicate (V) -/ /-- Valid input: both strings have lengths between 1 and 1000, consist only of English letters, and the true count of matching subsequences fits in 32 signed bits. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length ≤ 1000 && 1 ≤ input.2.length && input.2.length ≤ 1000 && 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') && input.1.toList.sublists.count input.2.toList ≤ 2 ^ 31 - 1 /-! ### Ideal specification (P_spec) -/ /-- `result` is the number of distinct subsequences of `s` equal to `t`: some finite collection of index lists contains exactly the strictly increasing positions of `s` spelling `t`, and `result` is the integer cast of its cardinality. -/ def numDistinctSubsequences_spec (input : Input) (result : Output) : Prop := ∃ C : Finset (List ℕ), (C.card : Int) = result ∧ ∀ idx : List ℕ, idx ∈ C ↔ IsSubsequenceIndices input.1 input.2 idx /-! ### Decidable specification (P_check) -/ /-- Boolean test for strict increase of a list of natural numbers. -/ def idxStrictlyIncreasing : List ℕ → Bool | [] => true | [_] => true | a :: b :: rest => decide (a < b) && idxStrictlyIncreasing (b :: rest) /-- Boolean counterpart of `IsSubsequenceIndices`: the positions strictly increase and the characters at those positions spell `t`. -/ def isSubsequenceIndicesB (s t : String) (idx : List ℕ) : Bool := idxStrictlyIncreasing idx && decide (idx.map (fun i => s.toList[i]?) = t.toList.map some) /-- The finite collection of all strictly increasing index lists into `s` whose characters spell `t`, realized as the spelling sublists of `List.range s.length`. -/ def subsequenceIndexFinset (s t : String) : Finset (List ℕ) := ((List.range s.length).sublists.filter fun idx => isSubsequenceIndicesB s t idx).toFinset /-- Executable checker for `numDistinctSubsequences_spec`: the specification's biconditional characterizes its collection uniquely, so compute it and compare cardinalities. -/ def numDistinctSubsequences_check (input : Input) (result : Output) : Bool := decide (((subsequenceIndexFinset input.1 input.2).card : Int) = result) theorem wx_increasing (idx : List Nat) : idxStrictlyIncreasing idx = true ↔ idx.Pairwise (· < ·) := by induction idx with | nil => simp [idxStrictlyIncreasing] | cons a tail ih => cases tail with | nil => simp [idxStrictlyIncreasing] | cons b rest => rw [idxStrictlyIncreasing, Bool.and_eq_true, decide_eq_true_eq, List.pairwise_cons_cons_iff_of_trans, ih] lemma wx_sublist_range {idx : List Nat} {n : Nat} (hi : idx.Pairwise (· < ·)) (hb : ∀ i ∈ idx, i < n) : idx.Sublist (List.range n) := by apply List.sublist_of_subperm_of_pairwise (hi.nodup.subperm ?_) hi List.pairwise_lt_range intro i hi' exact List.mem_range.mpr (hb i hi') theorem wx_indices_bounded {s t : String} {idx : List ℕ} (hm : idx.map (fun i => s.toList[i]?) = t.toList.map some) : ∀ i ∈ idx, i < s.length := by intro i hi have hmem : s.toList[i]? ∈ t.toList.map some := by rw [← hm] exact List.mem_map_of_mem hi obtain ⟨c, _, hc⟩ := List.mem_map.mp hmem obtain ⟨hlt, _⟩ := List.getElem?_eq_some_iff.mp hc.symm simpa only [String.length_toList] using hlt theorem wx_mem_template (increasing : ∀ idx, idxStrictlyIncreasing idx = true ↔ idx.Pairwise (· < ·)) (enumeration : ∀ (idx : List ℕ) (n : ℕ), idx.Pairwise (· < ·) → (∀ i ∈ idx, i < n) → idx.Sublist (List.range n)) (s t : String) (idx : List ℕ) : idx ∈ subsequenceIndexFinset s t ↔ IsSubsequenceIndices s t idx := by simp only [subsequenceIndexFinset, List.mem_toFinset, List.mem_filter, List.mem_sublists, isSubsequenceIndicesB, Bool.and_eq_true, decide_eq_true_eq, increasing, IsSubsequenceIndices] constructor · intro h exact h.2 · intro h exact ⟨enumeration idx s.length h.1 (wx_indices_bounded h.2), h⟩ theorem wx_root_template (bridge : ∀ (s t : String) (idx : List ℕ), idx ∈ subsequenceIndexFinset s t ↔ IsSubsequenceIndices s t idx) (input : Input) (result : Output) : numDistinctSubsequences_check input result ↔ numDistinctSubsequences_spec input result := by simp only [numDistinctSubsequences_check, decide_eq_true_eq, numDistinctSubsequences_spec] constructor · intro hc exact ⟨subsequenceIndexFinset input.1 input.2, hc, bridge input.1 input.2⟩ · rintro ⟨C, hc, hm⟩ have heq : C = subsequenceIndexFinset input.1 input.2 := by ext idx exact (hm idx).trans (bridge input.1 input.2 idx).symm simpa only [heq] using hc /-- On valid input the checker accepts exactly the specified outputs. -/ theorem numDistinctSubsequences_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : numDistinctSubsequences_check input result ↔ numDistinctSubsequences_spec input result := by exact wx_root_template (wx_mem_template wx_increasing (fun idx n hi hb => wx_sublist_range hi hb)) input result /-! ### Implementation helpers -/ /-- Inner DP loop for one character `c` of `s`: scan the prefixes of `t` ascending, carrying the old value of `dp[j-1]`, and add it into `dp[j]` whenever the prefix ends with `c`. -/ def dpUpdateRow (c : Char) (t : List Char) (dp : Array Int) : Array Int := let rec go (t : List Char) (j : Nat) (prev : Int) (dp : Array Int) : Array Int := match t with | [] => dp | x :: xs => let cur := dp.getD j 0 let dp' := if c == x then dp.set! j (cur + prev) else dp go xs (j + 1) cur dp' go t 1 (dp.getD 0 0) dp /-- Fold every character of `s` through `dpUpdateRow` and read off the count for the full prefix of `t`. -/ def countDistinctSubsequencesAux : List Char → List Char → Array Int → Int | [], t, dp => dp.getD t.length 0 | c :: cs, t, dp => countDistinctSubsequencesAux cs t (dpUpdateRow c t dp) /-! ### Main algorithm (impl) -/ /-- Distinct-subsequence count by dynamic programming over prefixes of `t`, with a one-dimensional rolling table updated once per character of `s`. -/ def countDistinctSubsequences (input : Input) : Output := let t := input.2.toList let dp := (Array.replicate (t.length + 1) (0 : Int)).set! 0 1 countDistinctSubsequencesAux input.1.toList t dp /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem countDistinctSubsequences_correct (input : Input) (h : isValidInput input) : numDistinctSubsequences_spec input (countDistinctSubsequences input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ("rabbbit", "rabbit") #guard isValidInput ("babgbag", "bag") #guard isValidInput ("abc", "abcd") /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ("a1b", "ab")) #guard !(isValidInput ("ab", "a1b")) #guard !(isValidInput ("a b", "ab")) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard numDistinctSubsequences_check ("rabbbit", "rabbit") 3 #guard numDistinctSubsequences_check ("babgbag", "bag") 5 #guard numDistinctSubsequences_check ("abc", "abcd") 0 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(numDistinctSubsequences_check ("rabbbit", "rabbit") 2) #guard !(numDistinctSubsequences_check ("babgbag", "bag") 4) #guard !(numDistinctSubsequences_check ("abc", "abcd") 8) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard countDistinctSubsequences ("rabbbit", "rabbit") == 3 #guard countDistinctSubsequences ("babgbag", "bag") == 5 #guard countDistinctSubsequences ("abc", "abcd") == 0 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard numDistinctSubsequences_check ("rabbbit", "rabbit") (countDistinctSubsequences ("rabbbit", "rabbit")) #guard numDistinctSubsequences_check ("babgbag", "bag") (countDistinctSubsequences ("babgbag", "bag")) #guard numDistinctSubsequences_check ("abc", "abcd") (countDistinctSubsequences ("abc", "abcd")) end PDistinctSubsequences