[Model] ClosestString

[zhangjieqingithub]

Motivation

ClosestString is a standard string-combinatorics model that is not currently in the catalog.

It is useful because it captures the consensus-string problem under Hamming distance: given several equal-length strings, find one center string that minimizes the worst Hamming distance to the inputs. This problem appears in computational biology, coding theory, and clustering over discrete sequences.

Associated rule:

• [Rule] ClosestString to ILP #1034

Definition

Name: ClosestString
Reference: Ming Li, Bin Ma, and Lusheng Wang, "On the closest string and substring problems," Journal of the ACM 49(2):157-171, 2002. https://doi.org/10.1145/506147.506150

Let Sigma = {0, ..., q-1} be a finite alphabet. The input is a list of strings
s_1, ..., s_n in Sigma^m
all having the same length m.

A solution is a center string
c in Sigma^m.

The objective is to minimize the maximum Hamming distance from the center to the input strings:

minimize max_i d_H(c, s_i).

So this is a minimization problem.

Variables

Let m be the common string length and q = alphabet_size.

• Count: m variables
• Per-variable domain: {0, ..., q-1}
• Meaning: variable c_j is the symbol chosen for the center string at position j

A configuration is always syntactically feasible if every symbol lies in the alphabet. Its objective value is the maximum Hamming distance to the input strings.

Schema (data type)

Type name: ClosestString

Field	Mathematical type	Description
alphabet_size	positive integer	Size q of the finite alphabet
strings	list of equal-length strings over {0,...,q-1}	Input strings s_1,...,s_n

Suggested size fields:

• alphabet_size
• num_strings
• string_length
• total_length = num_strings * string_length

Input validation should require:

• alphabet_size > 0 unless all strings and the center length are zero,
• all input strings have equal length,
• every symbol is < alphabet_size.

Complexity

The direct exact baseline enumerates all possible center strings and evaluates the maximum Hamming distance.

This gives:

O(alphabet_size^string_length * num_strings * string_length).

The registry complexity expression can use:

alphabet_size ^ string_length.

Extra Remark

This model is distinct from ClosestSubstring. In ClosestString, every input string has the same length as the center, so there is no window-selection decision.

Reduction Rule Crossref

• [Rule] ClosestString to ILP #1034

How to solve

• It can be solved by brute force over all center strings.
• It can be reduced exactly to ILP/i32 via [Rule] ClosestString to ILP #1034.

Example Instance

Use binary alphabet Sigma = {0,1} and input strings of length 3:

String	Value
s_1	000
s_2	011
s_3	101
s_4	110

Expected Outcome

An optimal center string is:

c = 000.

Its distances are:

• d_H(000, 000) = 0
• d_H(000, 011) = 2
• d_H(000, 101) = 2
• d_H(000, 110) = 2

So the objective value is 2.

No center has radius 1: the four input strings are pairwise arranged so that every binary length-3 string is at distance at least 2 from at least one input string. Therefore the optimum radius is exactly 2.

BibTeX

@article{LiMaWang2002ClosestStringSubstring,
  author  = {Ming Li and Bin Ma and Lusheng Wang},
  title   = {On the Closest String and Substring Problems},
  journal = {Journal of the ACM},
  volume  = {49},
  number  = {2},
  pages   = {157--171},
  year    = {2002},
  doi     = {10.1145/506147.506150},
  url     = {https://doi.org/10.1145/506147.506150}
}

[nithya16o1]

Hi! I'd like to work on this issue. I've looked at the existing model implementations in the codebase and I'm comfortable following the same pattern. Can you please assign this to me?

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	Pass	Novel problem (pred show ClosestString fails); concrete reduction crossref to #1034 (ClosestString -> ILP/i32); biology/coding-theory motivation given.
Non-trivial	Pass	Distinct from ClosestVectorProblem (lattice vs. Hamming) and StringToStringCorrection; not a variant of any existing string model.
Correctness	Pass	Cited paper (Li, Ma & Wang, JACM 49(2):157-171, 2002, DOI 10.1145/506147.506150) verified to exist with stated title/authors/year. NP-hardness independently corroborated (Frances & Litman 1997 reduction from 3-SAT to binary Closest String). Brute-force complexity O(alphabet_size^string_length * num_strings * string_length) is correct.
Well-written	Pass	All template sections present; symbols Sigma, q, m, n, c, s_i, d_H consistently defined before use; example exercises the core min-max-Hamming structure.

Overall: 4 passed, 0 warnings, 0 failed

---

Usefulness

• pred show ClosestString returns "Unknown problem" — confirmed novel.
• The issue explicitly links the planned reduction [Rule] ClosestString to ILP ([Rule] ClosestString to ILP #1034), which exists and targets ILP/i32, satisfying the orphan-prevention rule.
• The "How to solve" section ticks brute force and direct ILP via [Rule] ClosestString to ILP #1034. Per the skill rules, the ILP claim must be accompanied by a companion [Rule] <Model> to ILP issue — that companion is present and is linked in both the "Associated rule" and "Reduction Rule Crossref" sections.
• Motivation cites three concrete application areas: computational biology (consensus sequences), coding theory (covering radius), and clustering over discrete sequences. Concrete enough.

Non-trivial

• Searched the catalog for related models (pred list --json filtered to closest|string): only ClosestVectorProblem/{i32,f64} and StringToStringCorrection exist.
  • ClosestVectorProblem is over a lattice with Euclidean/l_p distance, not Hamming over a finite alphabet of strings.
  • StringToStringCorrection is an edit-distance variant, not a min-max over many input strings with a chosen center.
• The issue also calls out (Extra Remark) that this is distinct from ClosestSubstring ([Model] ClosestSubstring #1033) because there is no window-selection decision — i.e., the center has length m and is compared head-on against each s_i.
• Variables are m q-ary (not binary), objective is a min-max over n Hamming distances. No isomorphism with any existing model.

Correctness

Definition. Formal definition is mathematically clean: input is (Sigma, s_1,...,s_n) with all s_i in Sigma^m; configuration space is Sigma^m; objective is min_c max_i d_H(c, s_i). Feasibility and objective are correctly separated (every configuration is feasible; only the objective varies).

Schema feasibility. alphabet_size as positive integer is fine; strings as a list of equal-length strings over {0,...,q-1} is faithful to the math. The validation rules (equal length, symbols < alphabet_size) cover the natural input invariants. The schema can represent every instance the definition admits.

Complexity. O(alphabet_size^string_length * num_strings * string_length) is exactly the cost of brute-force enumeration over all q^m center strings followed by an O(n * m) evaluation per candidate. Registry-friendly form alphabet_size ^ string_length is correct (the per-candidate factor is polynomial and is typically suppressed when reporting the dominant exponential base, matching the style used for other variants in the catalog).

Reference verification.

• Li, Ma & Wang, "On the closest string and substring problems," JACM 49(2):157-171, 2002, DOI 10.1145/506147.506150 — confirmed via WebSearch; open-access PDFs at arXiv cs/0002012 and the ACM DL. This paper established the formal definition of ClosestString and ClosestSubstring, gave PTAS results, and is the standard primary reference.
• NP-hardness of Closest String (even for binary alphabet) is well-established via Frances & Litman, "On covering problems of codes," Theory of Computing Systems 30(2):113-119, 1997 — corroborated via WebSearch.
• FPT results in the parameterized-complexity literature (Gramm, Niedermeier, Rossmanith 2003) further confirm the problem is well-studied and that the issue's framing matches the standard one.

No misquoted or fabricated citations.

Recommendations (non-fatal)

• The catalog precedent for related variants often lists a sharper-than-brute-force exact-algorithm bound. For Closest String, Gramm/Niedermeier/Rossmanith (2003) give an FPT algorithm O(n * m + n * d^d) parameterized by the optimal radius d. Since the registry already accepts q^m style bounds (matching this issue), it is fine to keep alphabet_size ^ string_length as the brute-force baseline; an FPT bound can optionally be added as a secondary remark when implementing.
• When implementing, consider also accepting an empty input (num_strings == 0) — the natural answer is radius 0 for any center, and the issue's input-validation note already covers the all-zero-length case.

Well-written

• All required Model template sections are present and substantive: Motivation, Name, Reference, Definition, Variables, Schema, Complexity, How to solve, Example Instance, Expected Outcome, plus a BibTeX block.
• Symbols are introduced before use: Sigma, q, m, n, c, s_i, d_H are all defined in the Definition section and used consistently in the Variables, Schema, Complexity, and Example sections.
• Naming convention: ClosestString (no Maximum/Minimum prefix) is acceptable since the objective is min-max and the problem name follows the established literature convention (matching ClosestVectorProblem in the catalog).
• Suggested size fields (alphabet_size, num_strings, string_length, total_length) are sensible and match the standard snake_case convention used by other models.
• Example with Sigma = {0,1} and 4 length-3 strings was verified by hand:
  • Optimal centers: 000, 011, 101, 110 all achieve radius 2.
  • Suboptimal centers 001, 010, 100, 111 achieve radius 3.
  • No center achieves radius 1 (confirmed by exhaustive enumeration).
  • This satisfies the round-trip-testability requirement: 4 optimal and 4 suboptimal configurations exist, so a buggy reduction would not trivially pass.
• Expected outcome is concrete (c = 000, distances tabulated, objective value 2) and includes the lower-bound argument that no center has radius 1.

Recommendations (non-fatal)

• Minor: the Extra Remark cleanly distinguishes from ClosestSubstring, which helps maintainers triage [Model] ClosestSubstring #1033 (the companion model issue).

[isPANN]

/review-structural — commit d86b568 (post-impl, code-quality + bug sweep)

Verdict: pass — model implementation matches the issue specification cleanly with no correctness issues found.

Issue compliance

• Mathematical definition matches issue: yes — Min<i64> objective computes max_i d_H(c, s_i) exactly as specified; Sigma = {0, ..., q-1}, length-m center, validating constructor enforces the issue's three input-validation rules (equal length, alphabet bound, q > 0 when strings are non-empty).
• Schema fields match: yes — ProblemSchemaEntry has alphabet_size (usize) and strings (Vec<Vec<usize>>); ProblemSizeFieldEntry lists all four suggested size fields (alphabet_size, num_strings, string_length, total_length), all backed by inherent getters with matching names. Complexity expression alphabet_size ^ string_length lines up with the suggested registry expression (polynomial factor num_strings * string_length correctly omitted, matching the project's complexity convention for similar models like ClosestSubstring).
• Canonical example: ok — canonical_model_example_specs() ships the issue's exact 4-string binary length-3 instance with optimal center [0,0,0] and optimal value 2. Verified by enumeration: only c ∈ {000, 011, 101, 110} achieve radius 2; the other four binary length-3 strings have radius 3, so optimum is exactly 2 as claimed. Example is wired through misc::canonical_model_example_specs() and surfaces in CLI help via example_for("ClosestString").

Findings

• Blockers (correctness): none
• Nits (quality/HCI):
  • The paper entry is hand-authored rather than using load-model-example, which means the rendered example is kept in lockstep with canonical_model_example_specs() only by convention. The comment in the typst block calls this out explicitly, and the same pattern is already used elsewhere in the paper (see lines 833, 948, 1094), so this is a pre-existing project-level pattern, not a regression introduced by this PR.
  • total_length getter is documented as num_strings * string_length; for m = 0 (the degenerate alphabet_size = 0 branch the constructor explicitly allows), this returns n * 0 = 0, which is consistent. No edge case bug.
  • Min<i64> is more than enough headroom for the per-instance max distance (bounded by string_length), so no overflow risk. No action needed.
  • Bib key lima2002closeststring deviates from the issue's suggested LiMaWang2002ClosestStringSubstring, but the same key is already used by the existing closest_substring.rs entry — keeping consistency with the pre-existing key is the right call here.