import Mathlib /-! # Remove All Adjacent Duplicates In String You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them. We repeatedly make duplicate removals on s until we no longer can. Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique. ## Constraints - 1 <= s.length <= 10^5 - s consists of lowercase English letters. ## Provided examples - `s = "abbaca"` → `"ca"` - `s = "azxxzy"` → `"ay"` - `s = "mississippi"` → `"m"` ## Synthesized negative examples - invalid input: `s = ""` ([structural] a predicate that admits 1 <= s.length <= 10^5. empty below the one-character minimum) - invalid input: `s = "A"` ([structural] a predicate that admits s consists of lowercase English letters.. uppercase letter passes a mere alphabetic check) - invalid input: `s = " "` ([structural] a predicate that admits s consists of lowercase English letters.. whitespace passes predicates that trim before checking) - `s = "abbaca"` → `"abbaca"` is wrong ([structural] minimality stated as achievability alone. reachable by zero removals but not minimal) - `s = "azxxzy"` → `"azzy"` is wrong ([structural] off-by-one in the number of duplicate removals to perform. one step before the true final string) - `s = "mississippi"` → `"misp"` is wrong ([structural] answer need not be obtainable from the input by duplicate removals. amended 2026-08-18 alongside its base positive) -/ namespace PRemoveAllAdjacentDuplicatesInString abbrev Input := String abbrev Output := String /-! ### Specification helpers -/ /-- One duplicate removal, transcribing "choosing two adjacent and equal letters and removing them," with the prefix before and the suffix after the removed pair left unchanged. -/ inductive DuplicateRemovalStep : String → String → Prop | remove (pre suf : String) (c : Char) : DuplicateRemovalStep (pre ++ String.ofList [c, c] ++ suf) (pre ++ suf) /-- "We repeatedly make duplicate removals on s until we no longer can": a finite chain of single removals reaches `t`, and no further removal is possible from `t`. -/ def DuplicateRemovalRun (s t : String) : Prop := Relation.ReflTransGen DuplicateRemovalStep s t ∧ ∀ u : String, ¬ DuplicateRemovalStep t u /-! ### Validity predicate (V) -/ /-- Valid input: 1 <= s.length <= 10^5 and every character of s is a lowercase English letter. -/ def isValidInput (input : Input) : Bool := decide (1 ≤ input.length) && decide (input.length ≤ 100000) && input.toList.all (fun c => decide ('a'.toNat ≤ c.toNat ∧ c.toNat ≤ 'z'.toNat)) /-! ### Ideal specification (P_spec) -/ /-- `result` is the final string the stated repeated duplicate-removal process reaches from `input`, and the stated uniqueness rules out every other terminal string reachable by the same process. -/ def removeDuplicates_spec (input : Input) (result : Output) : Prop := DuplicateRemovalRun input result ∧ ∀ t : String, DuplicateRemovalRun input t → t = result /-! ### Decidable specification (P_check) -/ /-- All reducts of a character list by removing exactly one adjacent equal pair, one entry per pair position, prefix and suffix untouched. -/ def oneStepRemovals : List Char → List (List Char) | [] => [] | c₁ :: tail => match tail with | [] => [] | c₂ :: rest => (if c₁ = c₂ then [rest] else []) ++ (oneStepRemovals tail).map (c₁ :: ·) /-- Every character list reachable from `cs` within `fuel` removals, listed root-first with the sequence tree's duplicates kept. -/ def removalTree : List Char → Nat → List (List Char) | cs, 0 => [cs] | cs, fuel + 1 => cs :: (oneStepRemovals cs).flatMap (fun t => removalTree t fuel) /-- Executable checker for `removeDuplicates_spec`: `result` is reachable from `input` within `input.length / 2` removals, `result` admits no further removal, and every reachable final string equals it. -/ def removeDuplicates_check (input : Input) (result : Output) : Bool := let reached := removalTree input.toList (input.length / 2) let out := result.toList reached.contains out && (oneStepRemovals out).isEmpty && reached.all (fun t => if (oneStepRemovals t).isEmpty then t == out else true) lemma wx_oneStep_sound {xs ys : List Char} (h : ys ∈ oneStepRemovals xs) : ∃ pre c suf, xs = pre ++ c :: c :: suf ∧ ys = pre ++ suf := by induction xs generalizing ys with | nil => simp [oneStepRemovals] at h | cons x xs ih => cases xs with | nil => simp [oneStepRemovals] at h | cons y rest => by_cases hxy : x = y · rw [oneStepRemovals, if_pos hxy, List.mem_append] at h rcases h with h | h · simp only [List.mem_singleton] at h subst ys exact ⟨[], x, rest, by simp [hxy], by simp⟩ · rcases List.mem_map.mp h with ⟨zs, hzs, rfl⟩ rcases ih hzs with ⟨pre, c, suf, hsrc, hout⟩ exact ⟨x :: pre, c, suf, by simp [hsrc], by simp [hout]⟩ · rw [oneStepRemovals, if_neg hxy, List.nil_append] at h rcases List.mem_map.mp h with ⟨zs, hzs, rfl⟩ rcases ih hzs with ⟨pre, c, suf, hsrc, hout⟩ exact ⟨x :: pre, c, suf, by simp [hsrc], by simp [hout]⟩ lemma wx_oneStep_complete (pre suf : List Char) (c : Char) : pre ++ suf ∈ oneStepRemovals (pre ++ c :: c :: suf) := by induction pre with | nil => simp [oneStepRemovals] | cons x pre ih => cases pre with | nil => simp only [List.singleton_append, List.nil_append] at ih ⊢ change x :: suf ∈ (if x = c then [c :: suf] else []) ++ (oneStepRemovals (c :: c :: suf)).map (x :: ·) exact List.mem_append_right _ (List.mem_map.mpr ⟨suf, ih, rfl⟩) | cons y rest => change x :: y :: rest ++ suf ∈ (if x = y then [rest ++ c :: c :: suf] else []) ++ (oneStepRemovals (y :: rest ++ c :: c :: suf)).map (x :: ·) exact List.mem_append_right _ (List.mem_map.mpr ⟨y :: rest ++ suf, ih, rfl⟩) lemma wx_step (a b : String) : b.toList ∈ oneStepRemovals a.toList ↔ DuplicateRemovalStep a b := by constructor · intro h rcases wx_oneStep_sound h with ⟨pre, c, suf, ha, hb⟩ have ha' : a = String.ofList (pre ++ c :: c :: suf) := by rw [← a.ofList_toList, ha] have hb' : b = String.ofList (pre ++ suf) := by rw [← b.ofList_toList, hb] rw [ha', hb'] simpa only [← String.ofList_append, List.append_assoc, List.cons_append, List.nil_append] using (DuplicateRemovalStep.remove (String.ofList pre) (String.ofList suf) c) · intro h cases h with | remove pre suf c => simpa [String.toList_append, List.append_assoc] using (wx_oneStep_complete pre.toList suf.toList c) lemma wx_fuel_decrease {a b : String} (h : DuplicateRemovalStep a b) : b.length / 2 < a.length / 2 := by cases h with | remove pre suf c => simp only [String.length_append, String.length_ofList, List.length_cons, List.length_nil] omega lemma wx_fuel_sound (step : ∀ a b : String, b.toList ∈ oneStepRemovals a.toList ↔ DuplicateRemovalStep a b) (fuel : Nat) (a b : String) (h : b.toList ∈ removalTree a.toList fuel) : Relation.ReflTransGen DuplicateRemovalStep a b := by induction fuel generalizing a with | zero => simp only [removalTree, List.mem_singleton] at h have hab := congrArg String.ofList h simp only [String.ofList_toList] at hab subst b exact .refl | succ fuel ih => simp only [removalTree, List.mem_cons, List.mem_flatMap] at h rcases h with h | ⟨c, hc, hb⟩ · have hab := congrArg String.ofList h simp only [String.ofList_toList] at hab subst b exact .refl · have hb' : b.toList ∈ removalTree (String.ofList c).toList fuel := by simpa only [String.toList_ofList] using hb have hc' : DuplicateRemovalStep a (String.ofList c) := (step a (String.ofList c)).mp (by simpa only [String.toList_ofList] using hc) exact (ih (String.ofList c) hb').head hc' lemma wx_fuel_complete (step : ∀ a b : String, b.toList ∈ oneStepRemovals a.toList ↔ DuplicateRemovalStep a b) (fuel : Nat) (a b : String) (bound : a.length / 2 ≤ fuel) (h : Relation.ReflTransGen DuplicateRemovalStep a b) : b.toList ∈ removalTree a.toList fuel := by induction fuel generalizing a with | zero => rcases h.cases_head with he | ⟨c, hc, hb⟩ · subst b simp [removalTree] · have hd := wx_fuel_decrease hc omega | succ fuel ih => rcases h.cases_head with he | ⟨c, hc, hb⟩ · subst b simp [removalTree] · simp only [removalTree, List.mem_cons, List.mem_flatMap] refine Or.inr ⟨c.toList, (step a c).mpr hc, ih c ?_ hb⟩ have hd := wx_fuel_decrease hc omega lemma wx_tree_iff (step : ∀ a b : String, b.toList ∈ oneStepRemovals a.toList ↔ DuplicateRemovalStep a b) (a b : String) : b.toList ∈ removalTree a.toList (a.length / 2) ↔ Relation.ReflTransGen DuplicateRemovalStep a b := by constructor · exact wx_fuel_sound step (a.length / 2) a b · exact wx_fuel_complete step (a.length / 2) a b le_rfl lemma wx_terminal (step : ∀ a b : String, b.toList ∈ oneStepRemovals a.toList ↔ DuplicateRemovalStep a b) (s : String) : oneStepRemovals s.toList = [] ↔ ∀ t : String, ¬ DuplicateRemovalStep s t := by rw [List.eq_nil_iff_forall_not_mem] constructor · intro hn t ht exact hn t.toList ((step s t).mpr ht) · intro hn xs hx apply hn (String.ofList xs) exact (step s (String.ofList xs)).mp (by simpa using hx) lemma wx_root (step : ∀ a b : String, b.toList ∈ oneStepRemovals a.toList ↔ DuplicateRemovalStep a b) (tree : ∀ a b : String, b.toList ∈ removalTree a.toList (a.length / 2) ↔ Relation.ReflTransGen DuplicateRemovalStep a b) (input result : String) : removeDuplicates_check input result ↔ removeDuplicates_spec input result := by simp [removeDuplicates_check, removeDuplicates_spec, DuplicateRemovalRun] constructor · rintro ⟨⟨hr, hn⟩, hu⟩ refine ⟨⟨(tree input result).mp hr, (wx_terminal step result).mp hn⟩, ?_⟩ intro t ht hn apply String.toList_injective exact (hu t.toList ((tree input t).mpr ht)).resolve_left (not_not_intro ((wx_terminal step t).mpr hn)) · rintro ⟨⟨hr, hn⟩, hu⟩ refine ⟨⟨(tree input result).mpr hr, (wx_terminal step result).mpr hn⟩, ?_⟩ intro xs hx by_cases ht : oneStepRemovals xs = [] · right have hr : Relation.ReflTransGen DuplicateRemovalStep input (String.ofList xs) := (tree input (String.ofList xs)).mp (by simpa using hx) have hn := (wx_terminal step (String.ofList xs)).mp (by simpa using ht) have he := hu (String.ofList xs) hr hn simpa using congrArg String.toList he · exact Or.inl ht /-- 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 exact wx_root wx_step (wx_tree_iff wx_step) input result /-! ### Implementation helpers -/ /-- Folds one character into the cancellation stack, popping a matching top and pushing otherwise. -/ def dedupStack (stack : List Char) (c : Char) : List Char := match stack with | [] => [c] | top :: rest => if top = c then rest else c :: stack /-! ### Main algorithm (impl) -/ /-- Computes the final string by a left-to-right cancellation stack over the input characters. -/ def removeAdjacentDuplicates (input : Input) : Output := String.ofList ((input.toList.foldl dedupStack []).reverse) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem removeAdjacentDuplicates_correct (input : Input) (h : isValidInput input) : removeDuplicates_spec input (removeAdjacentDuplicates input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput "abbaca" #guard isValidInput "azxxzy" #guard isValidInput "mississippi" /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput "") #guard !(isValidInput "A") #guard !(isValidInput " ") /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard removeDuplicates_check "abbaca" "ca" #guard removeDuplicates_check "azxxzy" "ay" #guard removeDuplicates_check "mississippi" "m" /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(removeDuplicates_check "abbaca" "abbaca") #guard !(removeDuplicates_check "azxxzy" "azzy") #guard !(removeDuplicates_check "mississippi" "misp") /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard removeAdjacentDuplicates "abbaca" == "ca" #guard removeAdjacentDuplicates "azxxzy" == "ay" #guard removeAdjacentDuplicates "mississippi" == "m" /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard removeDuplicates_check "abbaca" (removeAdjacentDuplicates "abbaca") #guard removeDuplicates_check "azxxzy" (removeAdjacentDuplicates "azxxzy") #guard removeDuplicates_check "mississippi" (removeAdjacentDuplicates "mississippi") end PRemoveAllAdjacentDuplicatesInString