import Mathlib /-! # Distinct Subsequences Ii Given a string s, return the number of distinct non-empty subsequences of s. Since the answer may be very large, return it modulo 10^9 + 7. A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not. ## Constraints - 1 <= s.length <= 2000 - s consists of lowercase English letters. ## Provided examples - `s = "abc"` → `7` - `s = "aba"` → `6` - `s = "aaa"` → `3` ## Synthesized negative examples - invalid input: `s = ""` ([structural] a predicate that admits 1 <= s.length <= 2000. empty string below the minimum length) - invalid input: `s = "A"` ([structural] a predicate that admits s consists of lowercase English letters.. catches a predicate checking for ASCII letters rather than lowercase) - invalid input: `s = "abc "` ([structural] a predicate that admits s consists of lowercase English letters.. catches a predicate that trims then checks lowercase letters) - `s = "abc"` → `6` is wrong ([structural] subsequence was interpreted as contiguous substring. drops the non-contiguous subsequence ac) - `s = "aba"` → `5` is wrong ([structural] off-by-one in the count skips one valid subsequence. true answer is six) - `s = "aaa"` → `2` is wrong ([structural] off-by-one: the full string subsequence is not counted. proper subsequences only; 'aaa' omitted.) -/ namespace PDistinctSubsequencesIi abbrev Input := String abbrev Output := Nat /-! ### Specification helpers -/ /-- `t` can be obtained from `s` by deleting zero or more characters while preserving the relative order of the remaining ones. -/ def IsSubsequence (s t : String) : Prop := t.toList.Sublist s.toList /-! ### Validity predicate (V) -/ /-- Valid input: a nonempty string of at most 2000 lowercase English letters. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 2000 && input.toList.all (fun c => 'a' ≤ c && c ≤ 'z') /-! ### Ideal specification (P_spec) -/ /-- `result` is the count of distinct nonempty subsequences of `input` modulo 1,000,000,007: a finite collection of strings of that size exists whose members are exactly the nonempty subsequences of `input`. -/ def countDistinctSubsequences_spec (input : Input) (result : Output) : Prop := ∃ c : Finset String, (c.card ≡ result [MOD 1_000_000_007] ∧ result < 1_000_000_007) ∧ ∀ t : String, t ∈ c ↔ (t ≠ "" ∧ IsSubsequence input t) /-! ### Decidable specification (P_check) -/ /-- The distinct nonempty subsequences of `input`, enumerated as the nonempty sublists of its characters and deduplicated. -/ def distinctNonemptySubsequences (input : Input) : Finset String := ((input.toList.sublists.filter (fun l => !l.isEmpty)).map String.ofList).toFinset /-- Executable checker for `countDistinctSubsequences_spec`: the canonical collection of distinct nonempty subsequences has cardinality congruent to `result` modulo 1,000,000,007, with `result` below the modulus. -/ def countDistinctSubsequences_check (input : Input) (result : Output) : Bool := decide ((distinctNonemptySubsequences input).card % 1_000_000_007 = result ∧ result < 1_000_000_007) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem countDistinctSubsequences_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : countDistinctSubsequences_check input result ↔ countDistinctSubsequences_spec input result := by classical have hmem : ∀ t : String, t ∈ distinctNonemptySubsequences input ↔ (t ≠ "" ∧ IsSubsequence input t) := by intro t simpa [distinctNonemptySubsequences, IsSubsequence, String.ofList_eq, and_comm] simp only [countDistinctSubsequences_check, decide_eq_true_eq, countDistinctSubsequences_spec] constructor · rintro ⟨hc, hr⟩ refine ⟨distinctNonemptySubsequences input, ⟨?_, hr⟩, hmem⟩ simpa only [Nat.ModEq, Nat.mod_eq_of_lt hr] using hc · rintro ⟨c, ⟨hc, hr⟩, hm⟩ have heq : c = distinctNonemptySubsequences input := by ext t exact (hm t).trans (hmem t).symm subst c exact ⟨by simpa only [Nat.ModEq, Nat.mod_eq_of_lt hr] using hc, hr⟩ /-! ### Implementation helpers -/ /-- One-character DP transition: update the running total (including the empty subsequence) and the per-letter record of the total at the previous occurrence. -/ def step (state : Nat × Array Nat) (c : Char) : Nat × Array Nat := let total := state.1 let last := state.2 let idx := c.toNat - 'a'.toNat let newTotal := (2 * total + 1_000_000_007 - last[idx]!) % 1_000_000_007 (newTotal, last.set! idx total) /-- Fold `step` over the characters of `s`, starting from total 1 (the empty subsequence) with all per-letter records zero. -/ def countIncludingEmpty (s : String) : Nat := (s.toList.foldl step (1, Array.replicate 26 0)).1 /-! ### Main algorithm (impl) -/ /-- Distinct-subsequence count by the doubling recurrence with last-occurrence subtraction, returning the nonempty count modulo 1,000,000,007. -/ def numDistinctSubsequences (input : Input) : Output := (countIncludingEmpty input + 1_000_000_007 - 1) % 1_000_000_007 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem numDistinctSubsequences_correct (input : Input) (h : isValidInput input) : countDistinctSubsequences_spec input (numDistinctSubsequences input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput "abc" #guard isValidInput "aba" #guard isValidInput "aaa" /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput "") #guard !(isValidInput "A") #guard !(isValidInput "abc ") /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard countDistinctSubsequences_check "abc" 7 #guard countDistinctSubsequences_check "aba" 6 #guard countDistinctSubsequences_check "aaa" 3 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(countDistinctSubsequences_check "abc" 6) #guard !(countDistinctSubsequences_check "aba" 5) #guard !(countDistinctSubsequences_check "aaa" 2) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard numDistinctSubsequences "abc" == 7 #guard numDistinctSubsequences "aba" == 6 #guard numDistinctSubsequences "aaa" == 3 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard countDistinctSubsequences_check "abc" (numDistinctSubsequences "abc") #guard countDistinctSubsequences_check "aba" (numDistinctSubsequences "aba") #guard countDistinctSubsequences_check "aaa" (numDistinctSubsequences "aaa") end PDistinctSubsequencesIi