import Mathlib /-! # Reorganize String Given a string s, rearrange the characters of s so that any two adjacent characters are not the same. Return any possible rearrangement of s or return "" if not possible. ## Constraints - 1 <= s.length <= 500 - s consists of lowercase English letters. ## Provided examples - `s = "aab"` → `"aba"` - `s = "aaab"` → `""` - `s = "a"` → `"a"` ## Synthesized negative examples - invalid input: `s = ""` ([structural] a predicate that admits 1 <= s.length <= 500. empty string where at least one character is required) - invalid input: `s = "A"` ([structural] a predicate that admits s consists of lowercase English letters.. uppercase letter; a predicate using isalpha() accepts it) - invalid input: `s = "à"` ([structural] a predicate that admits s consists of lowercase English letters.. non-English lowercase letter; a predicate using islower() accepts it) - `s = "aab"` → `"aab"` is wrong ([structural] no requirement that adjacent characters differ. uses all characters but repeats 'a' adjacently) - `s = "aaab"` → `"ab"` is wrong ([structural] output is not required to use all characters of s. 'ab' has no adjacent equal but omits two a's) - `s = "a"` → `"b"` is wrong ([structural] drops the requirement that the output contain the input's characters. single lowercase letter, no adjacent equal, but not from input) -/ namespace PReorganizeString abbrev Input := String abbrev Output := String /-! ### Specification helpers -/ /-- `t` is a permutation of `s`'s characters with no two adjacent characters equal. -/ def IsValidRearrangement (s t : String) : Prop := s.toList.Perm t.toList ∧ t.toList.Chain' (fun a b => a ≠ b) /-! ### Validity predicate (V) -/ /-- Valid input: a nonempty string of at most 500 lowercase English letters. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 500 && input.toList.all (fun c => 'a' ≤ c && c ≤ 'z') /-! ### Ideal specification (P_spec) -/ /-- `result` is empty or a valid rearrangement of `input`, and it is empty if and only if no valid rearrangement of `input` exists. -/ def reorganizeString_spec (input : Input) (result : Output) : Prop := (result = "" ∨ IsValidRearrangement input result) ∧ (result = "" ↔ ¬∃ t : String, IsValidRearrangement input t) /-! ### Decidable specification (P_check) -/ /-- Whether adjacent characters in `chars` are all different. -/ def hasNoAdjacentDuplicates (chars : List Char) : Bool := (chars.zip (chars.drop 1)).all (fun pair => pair.1 != pair.2) /-- Whether some permutation of `input`'s characters has no adjacent duplicates. -/ def existsValidRearrangement (input : Input) : Bool := input.toList.permutations.any (fun chars => hasNoAdjacentDuplicates chars) /-- Executable checker for `reorganizeString_spec`. -/ def reorganizeString_check (input : Input) (result : Output) : Bool := (result == "" || input.toList.permutations.any (fun chars => chars == result.toList && hasNoAdjacentDuplicates chars)) && ((result == "") == !existsValidRearrangement input) theorem root_of_bridges (bridge : ∀ cs : List Char, hasNoAdjacentDuplicates cs = true ↔ cs.Chain' (fun a b => a ≠ b)) (input result : String) : reorganizeString_check input result ↔ reorganizeString_spec input result := by have hex : existsValidRearrangement input = true ↔ ∃ t : String, IsValidRearrangement input t := by simp only [existsValidRearrangement, List.any_eq_true, List.mem_permutations, bridge] constructor · rintro ⟨cs, hp, hc⟩ exact ⟨String.ofList cs, by simpa [IsValidRearrangement] using And.intro hp.symm hc⟩ · rintro ⟨t, hp, hc⟩ exact ⟨t.toList, hp.symm, hc⟩ cases he : existsValidRearrangement input <;> simp_all [reorganizeString_check, reorganizeString_spec, List.mem_permutations, bridge, IsValidRearrangement, List.perm_comm] theorem adjacency_bridge (cs : List Char) : hasNoAdjacentDuplicates cs = true ↔ cs.Chain' (fun a b => a ≠ b) := by induction cs with | nil => simp [hasNoAdjacentDuplicates, List.Chain'] | cons a cs ih => cases cs <;> simp_all [hasNoAdjacentDuplicates, List.Chain', List.isChain_cons_cons] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem reorganizeString_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : reorganizeString_check input result ↔ reorganizeString_spec input result := by exact root_of_bridges adjacency_bridge input result /-! ### Implementation helpers -/ /-- Append `n` copies of `c` in front of the accumulated expansion. -/ def repeatChar (c : Char) : Nat → List Char | 0 => [] | n + 1 => c :: repeatChar c n /-- Insert one frequency pair into a list sorted by descending count. -/ def insertByCount (p : Char × Nat) : List (Char × Nat) → List (Char × Nat) | [] => [p] | q :: qs => if p.2 ≤ q.2 then q :: insertByCount p qs else p :: q :: qs /-- Sort frequency pairs by descending count. -/ def sortByCountDesc : List (Char × Nat) → List (Char × Nat) | [] => [] | p :: ps => insertByCount p (sortByCountDesc ps) /-- Count occurrences of each lowercase letter in `s`. -/ def countFrequencies (s : String) : List (Char × Nat) := let cs := s.toList ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'].map (fun c => (c, cs.foldl (fun count x => if x == c then count + 1 else count) 0)) /-- Expand frequency pairs into the characters they count. -/ def buildExpanded (freqs : List (Char × Nat)) : List Char := freqs.foldl (fun acc p => acc ++ repeatChar p.1 p.2) [] /-- Interleave two halves, keeping any surplus from the first half at the end. -/ def interleaveHalves : List Char → List Char → List Char | [], ys => ys | x :: xs, [] => x :: xs | x :: xs, y :: ys => x :: y :: interleaveHalves xs ys /-! ### Main algorithm (impl) -/ /-- Rearrange by frequency feasibility, descending-count expansion, and half interleaving. -/ def rearrangeString (input : Input) : Output := let n := input.length let freqs := countFrequencies input let maxCount := freqs.foldl (fun acc p => Nat.max acc p.2) 0 if maxCount > (n + 1) / 2 then "" else let expanded := buildExpanded (sortByCountDesc freqs) let half := (n + 1) / 2 let candidate := interleaveHalves (expanded.take half) (expanded.drop half) if hasNoAdjacentDuplicates candidate then String.mk candidate else "" /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem rearrangeString_correct (input : Input) (h : isValidInput input) : reorganizeString_spec input (rearrangeString input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput "aab" #guard isValidInput "aaab" #guard isValidInput "a" /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput "") #guard !(isValidInput "A") #guard !(isValidInput "à") /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard reorganizeString_check "aab" "aba" #guard reorganizeString_check "aaab" "" #guard reorganizeString_check "a" "a" /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(reorganizeString_check "aab" "aab") #guard !(reorganizeString_check "aaab" "ab") #guard !(reorganizeString_check "a" "b") /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard rearrangeString "aab" == "aba" #guard rearrangeString "aaab" == "" #guard rearrangeString "a" == "a" /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard reorganizeString_check "aab" (rearrangeString "aab") #guard reorganizeString_check "aaab" (rearrangeString "aaab") #guard reorganizeString_check "a" (rearrangeString "a") end PReorganizeString