CF 103053B - Spelling Error

Rating: -
Tags: -
Solve time: 48s
Verified: yes

Solution

Problem Understanding

We are given a list of words, all of the same fixed length, collected from repeated observations of spoken or written mentions. Because the source is unreliable, the same intended word can appear in slightly different forms, either as a different word entirely or as a misspelling of the same word.

For every word in the list, we define its “similarity score” as the number of words in the entire list (including itself) that differ from it in at most one character position. Two words are considered close if, when aligned character by character, they differ in zero positions (identical words) or exactly one position.

The task is to identify which word achieves the maximum such score. If multiple words achieve the same maximum score, we must return the lexicographically smallest among them. We also need to count how many words achieve this maximum score.

The input size constraint is important: the total amount of characters across all strings is at most 2×10^5. This immediately tells us that any approach that compares every pair of strings naively, which would be O(N^2 · K), will fail when N is large. Even N around 2×10^5 with K = 1 would already be too slow for quadratic behavior.

A subtle edge case appears when multiple identical strings exist. Each identical copy contributes to the score of the others, and also to itself. Another tricky case arises when two strings differ in exactly one position but appear multiple times, since each occurrence contributes separately to the score.

A naive mistake is to interpret “differ by at most one letter” as “Hamming distance ≤ 1” but then accidentally treat duplicates incorrectly or forget to count self-inclusion. Another common pitfall is recomputing Hamming distance for every pair without early pruning, which leads to timeouts.

Approaches

The brute-force idea is straightforward. For each string, compare it with every other string, count how many differ in at most one position, and track the best result. This is correct because it directly follows the definition of the score. However, comparing two strings costs O(K), and doing it for all pairs costs O(N^2 · K). With N up to around 2×10^5 in total character budget, this is far beyond feasible. Even in smaller intended subtasks, this approach only survives when N is small.

The key observation is that two strings differ in at most one position if we can “guess” the mismatch position, or verify equality quickly using a hash-like grouping strategy. Instead of comparing full strings repeatedly, we can exploit the structure of “almost identical strings.”

For each position in the string, we can create a pattern where we remove that character and use the remaining K−1 characters as a signature. If two strings differ in exactly one position, then there exists at least one index where removing that index produces identical signatures for both strings. This allows us to group candidates efficiently by these partial signatures, reducing repeated comparisons to manageable counts.

We also maintain counts of exact duplicates separately, since identical strings must contribute fully to each other’s score without needing the “one mismatch” mechanism.

This reduces the problem from pairwise comparisons to hash aggregation over K positions per string.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(N^2 · K)	O(1)	Too slow
Signature Hashing per position	O(N · K)	O(N · K)	Accepted

Algorithm Walkthrough

Read all strings and store their frequency in a hash map. This lets us handle duplicates cleanly, since identical strings contribute multiplicatively to scores.
For each string, compute its contribution from identical strings by adding its frequency. This accounts for all pairs with Hamming distance 0.
For handling strings differing by exactly one position, iterate over each index of the string and build a “masked version” by removing that character. Store counts of these masked patterns in a hash map grouped by index.
For each string, compute its one-mismatch contribution by summing over all positions the number of strings sharing the same masked pattern, then subtracting overcounted exact matches where needed. This ensures we only count strings that differ in exactly one position, not identical ones.
Combine both contributions to get the final score of each distinct string.
Track the maximum score while iterating over all strings.
Among all strings achieving the maximum score, pick the lexicographically smallest, and count how many distinct strings achieve that maximum.

Why it works

The correctness comes from a structural property of Hamming distance 1 comparisons: any two strings that differ in exactly one position become identical after removing that position. Therefore, every valid pair is guaranteed to be captured in at least one of the K masked views. At the same time, identical strings are handled separately via frequency counts, so they are not missed or double-counted incorrectly. This separation ensures every pair contributes exactly once to the final score.

Python Solution

import sys
input = sys.stdin.readline

from collections import defaultdict, Counter

def solve():
    n, k = map(int, input().split())
    arr = [input().strip() for _ in range(n)]

    freq = Counter(arr)

    # For each position, map "string with that position removed" -> count
    masks = [defaultdict(int) for _ in range(k)]

    for s in arr:
        for i in range(k):
            key = s[:i] + s[i+1:]
            masks[i][key] += 1

    score = {}

    for s in freq:
        base = freq[s]  # identical matches
        total = base

        for i in range(k):
            key = s[:i] + s[i+1:]
            total += masks[i][key]

        # subtract overcount: freq[s] was added k times in masks
        total -= freq[s] * k

        score[s] = total

    max_score = max(score.values())

    best_strings = [s for s in score if score[s] == max_score]
    best_strings.sort()

    print(best_strings[0])
    print(len(best_strings))

if __name__ == "__main__":
    solve()

The code starts by compressing identical strings using a frequency table, which is essential because every duplicate contributes independently to the score.

Then it builds K different hash maps, each representing strings with one position removed. This is the key acceleration: instead of comparing strings directly, we compare their compressed fingerprints.

The subtraction step is necessary because identical strings appear in every masked bucket, so they are overcounted K times. Removing that duplication restores correctness.

Finally, we compute all scores, identify the maximum, and resolve ties by lexicographical order as required.

Worked Examples

Example 1

Input:

5 5
takos
tacos
fishy
aaaaa
fisty

We compute frequencies first, all are 1.

Now consider masked comparisons. For position where "takos" and "tacos" differ (index 1), removing that position produces identical signature "t__os", so they contribute to each other's mismatch score.

String	Base freq	Mask matches	Total score
takos	1	2	2
tacos	1	2	2
fishy	1	2	2
aaaaa	1	1	1
fisty	1	2	2

The maximum score is 2. Among those, lexicographically smallest is "fishy".

This shows how a single-letter mismatch creates a shared masked signature.

Example 2 (constructed)

Input:

4 3
abc
acc
adc
abc

String	Base freq	Mask matches	Score
abc	2	4	4
acc	1	3	3
adc	1	3	3

Here duplicates amplify the contribution of "abc", showing why frequency handling is essential.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N · K)	Each string is processed across K masked positions
Space	O(N · K)	Storage of masked hash maps

The constraint N · K ≤ 2×10^5 guarantees that building K hashes per string is fast enough. Even with constant overhead per dictionary operation, this fits comfortably in a 1-2 second limit.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from collections import defaultdict, Counter

    n, k = map(int, input().split())
    arr = [input().strip() for _ in range(n)]

    freq = Counter(arr)
    masks = [defaultdict(int) for _ in range(k)]

    for s in arr:
        for i in range(k):
            masks[i][s[:i] + s[i+1:]] += 1

    score = {}
    for s in freq:
        total = freq[s]
        for i in range(k):
            total += masks[i][s[:i] + s[i+1:]]
        total -= freq[s] * k
        score[s] = total

    mx = max(score.values())
    best = sorted([s for s in score if score[s] == mx])
    return best[0] + "\n" + str(len(best))

# provided sample
assert run("""5 5
takos
tacos
fishy
aaaaa
fisty
""") == "fishy\n4"

# all identical
assert run("""3 3
abc
abc
abc
""") == "abc\n1"

# all different, no near matches
assert run("""3 3
abc
def
ghi
""") == "abc\n1"

# single mismatch cluster
assert run("""4 3
abc
acc
adc
aec
""") is not None

Test input	Expected output	What it validates
all identical	abc / 1	duplicate handling
no matches	abc / 1	fallback lexicographic
mismatch cluster	depends	one-letter grouping correctness

Edge Cases

A key edge case is when all strings are identical. In that case, every string has the same maximum score equal to N, and the lexicographically smallest string must be chosen. The algorithm handles this because frequency dominates and masked contributions cancel out correctly after subtraction.

Another case is when two strings differ in more than one position. They must not be counted at all, and the masking technique ensures they never share a full signature in any single position removal, so they do not contribute incorrectly.

Finally, when multiple groups of near-identical strings exist, the scoring remains independent per string due to frequency-based aggregation, ensuring no cross-contamination between unrelated clusters.