import Mathlib /-! # Remove All Adjacent Duplicates In String Ii You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together. We repeatedly make k duplicate removals on s until we no longer can. Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique. ## Constraints - 1 <= s.length <= 10^5 - 2 <= k <= 10^4 - s only contains lowercase English letters. ## Provided examples - `s = "abcd", k = 2` → `"abcd"` - `s = "aab", k = 2` → `"b"` - `s = "a", k = 2` → `"a"` ## Synthesized negative examples - invalid input: `s = "", k = 2` ([structural] a predicate that admits 1 <= s.length <= 10^5. empty string where at least one letter is required; a predicate that omits the length check accepts it) - invalid input: `s = "abcd", k = 1` ([structural] a predicate that admits 2 <= k <= 10^4. one below the stated minimum; a predicate that skips k's lower bound accepts it) - invalid input: `s = "é", k = 2` ([structural] a predicate that admits s only contains lowercase English letters.. a lowercase non-English letter; a predicate using islower() accepts it) - `s = "abcd", k = 2` → `"abc"` is wrong ([structural] no reachability requirement, any terminal subsequence accepted. no valid removals from abcd produce abc) - `s = "aab", k = 2` → `"aab"` is wrong ([structural] maximality is not enforced; an intermediate string is accepted. 一次删除都不做就返回原串, 但 aa 还可以删) - `s = "a", k = 2` → `""` is wrong ([structural] specification omits reachability and accepts any irreducible string. empty string is irreducible but not reachable from s) -/ namespace PRemoveAllAdjacentDuplicatesInStringIi abbrev Input := (String) × (Nat) abbrev Output := String /-! ### Specification helpers -/ /-- One k duplicate removal; transcribes "choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together". -/ inductive Step : String → Nat → String → Prop where /-- The removed block is `k` consecutive copies of one letter `c`; the result concatenates the left and right sides of the deleted substring. -/ | remove (left right : String) (c : Char) (k : Nat) : Step (left ++ String.replicate k c ++ right) k (left ++ right) /-- Zero or more k duplicate removals; transcribes "We repeatedly make k duplicate removals on s" as the reflexive-transitive closure of `Step`. -/ def Reachable (s : String) (k : Nat) (t : String) : Prop := Relation.ReflTransGen (fun a b => Step a k b) s t /-! ### Validity predicate (V) -/ /-- Valid input: 1 <= s.length <= 10^5, 2 <= k <= 10^4, and every character of s is a lowercase English letter. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length ≤ 10 ^ 5 && 2 ≤ input.2 && input.2 ≤ 10 ^ 4 && input.1.all (fun c => 'a' ≤ c && c ≤ 'z') /-! ### Ideal specification (P_spec) -/ /-- `result` is the final string after repeatedly making k duplicate removals on s until none remains possible, and the statement's guarantee makes it the only such string. -/ def removeDuplicates_spec (input : Input) (result : Output) : Prop := (Reachable input.1 input.2 result ∧ ∀ t, ¬ Step result input.2 t) ∧ ∀ t, Reachable input.1 input.2 t → (∀ u, ¬ Step t input.2 u) → t = result /-! ### Decidable specification (P_check) -/ /-- Whether every character of `l` is the same. -/ def allEqual (l : List Char) : Bool := match l with | [] => true | c :: cs => cs.all (fun d => d == c) /-- All strings obtained from `cs` by one k duplicate removal, one per position whose k-block is a single repeated letter. -/ def stepReducts (cs : List Char) (k : Nat) : List (List Char) := (List.range (cs.length + 1 - k)).filterMap fun i => let block := (cs.drop i).take k if block.length == k && allEqual block then some (cs.take i ++ cs.drop (i + k)) else none /-- All strings reachable from the initial frontier in at most `fuel` removal steps, accumulating the visited strings in `seen`. -/ def reachableUpTo (k : Nat) (fuel : Nat) (seen frontier : List (List Char)) : List (List Char) := match fuel with | 0 => seen | fuel + 1 => let next := ((frontier.flatMap fun cs => stepReducts cs k).eraseDups).filter (fun t => !(seen.contains t)) reachableUpTo k fuel (seen ++ next) next /-- Whether no k duplicate removal applies to `cs`. -/ def irreducible (cs : List Char) (k : Nat) : Bool := (stepReducts cs k).isEmpty /-- Executable checker for `removeDuplicates_spec`: `result` is reachable, terminal, and the only reachable terminal string. -/ def removeDuplicates_check (input : Input) (result : Output) : Bool := let start := input.1.toList let reach := reachableUpTo input.2 (start.length / input.2) [start] [start] let r := result.toList (reach.contains r && irreducible r input.2) && reach.all (fun t => (!(irreducible t input.2)) || t == r) lemma bfs_keep (k n : Nat) (seen frontier : List (List Char)) (a : List Char) (ha : a ∈ seen) : a ∈ reachableUpTo k n seen frontier := by induction n generalizing seen frontier with | zero => exact ha | succ n ih => exact ih _ _ (List.mem_append_left _ ha) lemma bfs_sound (k n : Nat) (s : String) (hs : ∀ a b : String, b.toList ∈ stepReducts a.toList k ↔ Step a k b) (seen frontier : List (List Char)) (hi : ∀ a ∈ seen, Reachable s k (String.ofList a)) (hf : ∀ a ∈ frontier, a ∈ seen) : ∀ a ∈ reachableUpTo k n seen frontier, Reachable s k (String.ofList a) := by induction n generalizing seen frontier with | zero => exact hi | succ n ih => apply ih · intro a ha simp only [List.mem_append] at ha rcases ha with ha | ha · exact hi a ha · simp only [List.mem_filter, List.mem_eraseDups, List.mem_flatMap] at ha obtain ⟨⟨b, hb, hab⟩, _⟩ := ha exact (hi b (hf b hb)).tail ((hs _ _).mp (by simpa using hab)) · intro a ha exact List.mem_append_right _ ha lemma bfs_closed (k n : Nat) (μ : List Char → Nat) (hd : ∀ a b, b ∈ stepReducts a k → μ b < μ a) (seen frontier : List (List Char)) (hi : ∀ a ∈ seen, ∀ b ∈ stepReducts a k, b ∈ seen ∨ a ∈ frontier) (hb : ∀ a ∈ frontier, μ a ≤ n) : ∀ a ∈ reachableUpTo k n seen frontier, ∀ b ∈ stepReducts a k, b ∈ reachableUpTo k n seen frontier := by induction n generalizing seen frontier with | zero => intro a ha b hab rcases hi a ha b hab with h | h · exact h · have := hb a h have := hd a b hab omega | succ n ih => let next := ((frontier.flatMap fun cs => stepReducts cs k).eraseDups).filter (fun t => !(seen.contains t)) have hn (b : List Char) : b ∈ next ↔ (∃ a ∈ frontier, b ∈ stepReducts a k) ∧ b ∉ seen := by simp [next] change ∀ a ∈ reachableUpTo k n (seen ++ next) next, ∀ b ∈ stepReducts a k, b ∈ reachableUpTo k n (seen ++ next) next apply ih · intro a ha b hab rcases List.mem_append.mp ha with ha | ha · left rcases hi a ha b hab with h | h · exact List.mem_append_left _ h · by_cases hx : b ∈ seen · exact List.mem_append_left _ hx · exact List.mem_append_right _ ((hn b).mpr ⟨⟨a,h,hab⟩,hx⟩) · exact Or.inr ha · intro a ha obtain ⟨⟨b, hbf, hab⟩, _⟩ := (hn a).mp ha have := hb b hbf have := hd b a hab omega lemma step_length (s t : String) (k : Nat) (h : Step s k t) : t.toList.length + k = s.toList.length := by cases h simp [String.toList_append, String.replicate] omega lemma reach_bridge (k : Nat) (hk : 0 < k) (hs : ∀ s t : String, t.toList ∈ stepReducts s.toList k ↔ Step s k t) (s t : String) : t.toList ∈ reachableUpTo k (s.toList.length / k) [s.toList] [s.toList] ↔ Reachable s k t := by let μ : List Char → Nat := fun a => a.length / k have hd : ∀ a b, b ∈ stepReducts a k → μ b < μ a := by intro a b hab have hh := (hs (String.ofList a) (String.ofList b)).mp (by simpa using hab) have hl := step_length _ _ _ hh simp only [String.toList_ofList] at hl dsimp [μ] rw [← hl, Nat.add_div_right _ hk] omega constructor · intro h have hh := bfs_sound k (s.toList.length / k) s hs [s.toList] [s.toList] (by intro a ha; simp only [List.mem_singleton] at ha; subst a; simpa [Reachable] using (Relation.ReflTransGen.refl : Reachable s k s)) (by intro a ha; exact ha) t.toList h simpa using hh · intro h have hc := bfs_closed k (s.toList.length / k) μ hd [s.toList] [s.toList] (by intro a ha b hab; exact Or.inr ha) (by intro a ha; simp only [List.mem_singleton] at ha; subst a; exact le_rfl) induction h with | refl => exact bfs_keep _ _ _ _ _ (by simp) | @tail b c h hbc ih => exact hc _ ih _ ((hs b c).mpr hbc) lemma root_from_relations (input : Input) (result : Output) (hs : ∀ s t : String, t.toList ∈ stepReducts s.toList input.2 ↔ Step s input.2 t) (hr : ∀ t : String, t.toList ∈ reachableUpTo input.2 (input.1.toList.length / input.2) [input.1.toList] [input.1.toList] ↔ Reachable input.1 input.2 t) : removeDuplicates_check input result ↔ removeDuplicates_spec input result := by have ht (s : String) : irreducible s.toList input.2 = true ↔ ∀ t, ¬ Step s input.2 t := by simp only [irreducible, List.isEmpty_iff] rw [List.eq_nil_iff_forall_not_mem] constructor · intro h t; simpa only [← hs] using h t.toList · intro h t hm have := h (String.ofList t) exact this ((hs _ _).mp (by simpa using hm)) simp only [removeDuplicates_check, Bool.and_eq_true, List.contains_iff_mem, List.all_eq_true, Bool.or_eq_true, Bool.not_eq_true', beq_iff_eq] rw [hr, ht] unfold removeDuplicates_spec constructor · rintro ⟨h, hu⟩ refine ⟨h, ?_⟩ intro t hreach hterm have hh := hu t.toList ((hr t).mpr hreach) have hn := (ht t).mpr hterm simp only [hn, Bool.true_eq_false, false_or] at hh simpa using congrArg String.ofList hh · rintro ⟨h, hu⟩ refine ⟨h, ?_⟩ intro t hm by_cases hi : irreducible t input.2 = true · right have hh := hu (String.ofList t) ((hr _).mp (by simpa using hm)) ((ht _).mp (by simpa using hi)) simpa using congrArg String.toList hh · left; exact Bool.eq_false_iff.mpr hi lemma root_of_bridges (input : Input) (result : Output) (h : isValidInput input) (hs : ∀ s t : String, t.toList ∈ stepReducts s.toList input.2 ↔ Step s input.2 t) : removeDuplicates_check input result ↔ removeDuplicates_spec input result := by have hk : 0 < input.2 := by simp only [isValidInput, Bool.and_eq_true, decide_eq_true_eq] at h omega exact root_from_relations input result hs (reach_bridge input.2 hk hs input.1) lemma allEqual_cons_iff (c : Char) (cs : List Char) : allEqual (c :: cs) ↔ ∀ d ∈ cs, d = c := by simp [allEqual] lemma allEqual_cons_eq_replicate (c : Char) (cs : List Char) (hl : allEqual (c :: cs)) : c :: cs = List.replicate (c :: cs).length c := by rw [List.eq_replicate_iff] constructor · simp · intro d hd simp only [allEqual, Bool.and_eq_true, List.all_eq_true, beq_iff_eq] at hl rcases List.mem_cons.mp hd with hdc | hd · exact hdc · exact hl d hd lemma allEqual_replicate (k : Nat) (c : Char) : allEqual (List.replicate k c) := by cases k <;> simp [List.replicate_succ, allEqual] lemma step_bridge (k : Nat) (hk : 0 < k) (s t : String) : t.toList ∈ stepReducts s.toList k ↔ Step s k t := by constructor · intro h obtain ⟨i, hi, heq⟩ := List.mem_filterMap.mp h dsimp at heq split_ifs at heq with hguard simp at hguard obtain ⟨hlen, hall⟩ := hguard have hlen' : ((s.toList.drop i).take k).length = k := by simp [List.length_take, List.length_drop, min_eq_left hlen] have hnempty : (s.toList.drop i).take k ≠ [] := by intro hz simp [hz] at hlen' omega generalize hblockeq : (s.toList.drop i).take k = block at hlen' hall heq cases block with | nil => exact (hnempty hblockeq).elim | cons c cs => have hrep0 := allEqual_cons_eq_replicate c cs hall have hrep : (s.toList.drop i).take k = List.replicate k c := by rw [hblockeq, hrep0, hlen'] let left := String.ofList (s.toList.take i) let right := String.ofList (s.toList.drop (i + k)) have hslist : s.toList = s.toList.take i ++ List.replicate k c ++ s.toList.drop (i + k) := by rw [← hrep, List.append_assoc, List.drop_take_append_drop, List.take_append_drop] have hs : s = left ++ String.replicate k c ++ right := by apply String.toList_injective simpa [left, right, String.replicate] using hslist have ht : t = left ++ right := by apply String.toList_injective simpa [left, right] using heq.symm rw [hs, ht] exact Step.remove left right c k · intro h cases h with | remove left right c k => apply List.mem_filterMap.mpr refine ⟨left.toList.length, ?_, ?_⟩ · simp [String.toList_append, String.replicate] omega · dsimp have hblock : (((left ++ String.replicate k c ++ right).toList.drop left.toList.length).take k) = List.replicate k c := by simp [String.toList_append, String.replicate] simp [String.toList_append, String.replicate, allEqual_replicate] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem removeDuplicates_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : removeDuplicates_check input result ↔ removeDuplicates_spec input result := by have hk : 0 < input.2 := by simp only [isValidInput, Bool.and_eq_true, decide_eq_true_eq] at h omega exact root_of_bridges input result h (step_bridge input.2 hk) /-! ### Implementation helpers -/ /-- Process the character list left to right, maintaining the run stack of (character, consecutive count) pairs with the most recent run at the head. -/ def removeKDuplicatesAux (k : Nat) (stack : List (Char × Nat)) : List Char → List (Char × Nat) | [] => stack | c :: cs => match stack with | (d, n) :: rest => if d == c then if n + 1 == k then removeKDuplicatesAux k rest cs else removeKDuplicatesAux k ((d, n + 1) :: rest) cs else removeKDuplicatesAux k ((c, 1) :: stack) cs | [] => removeKDuplicatesAux k [(c, 1)] cs /-- Emit the final run stack as a string, each character repeated by its count, in original left-to-right order. -/ def stackToString (stack : List (Char × Nat)) : String := (stack.reverse.flatMap fun (c, n) => List.replicate n c).asString /-! ### Main algorithm (impl) -/ /-- Final string after repeated k duplicate removals, computed in one pass by a stack of runs. -/ def removeKDuplicates (input : Input) : Output := stackToString (removeKDuplicatesAux input.2 [] input.1.toList) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem removeKDuplicates_correct (input : Input) (h : isValidInput input) : removeDuplicates_spec input (removeKDuplicates input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ("abcd", 2) #guard isValidInput ("aab", 2) #guard isValidInput ("a", 2) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ("", 2)) #guard !(isValidInput ("abcd", 1)) #guard !(isValidInput ("é", 2)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard removeDuplicates_check ("abcd", 2) "abcd" #guard removeDuplicates_check ("aab", 2) "b" #guard removeDuplicates_check ("a", 2) "a" /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(removeDuplicates_check ("abcd", 2) "abc") #guard !(removeDuplicates_check ("aab", 2) "aab") #guard !(removeDuplicates_check ("a", 2) "") /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard removeKDuplicates ("abcd", 2) == "abcd" #guard removeKDuplicates ("aab", 2) == "b" #guard removeKDuplicates ("a", 2) == "a" /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard removeDuplicates_check ("abcd", 2) (removeKDuplicates ("abcd", 2)) #guard removeDuplicates_check ("aab", 2) (removeKDuplicates ("aab", 2)) #guard removeDuplicates_check ("a", 2) (removeKDuplicates ("a", 2)) end PRemoveAllAdjacentDuplicatesInStringIi