Rating: -
Tags: -
Solve time: 4m 45s
Verified: yes

Solution

Problem Understanding

We are given (N) distinct words. Every word is an anagram of every other word, and no letter occurs twice inside a word. We want to choose as many words as possible so that no two chosen words can be obtained from one another by swapping exactly one pair of positions.

Because every word contains the same distinct letters, two different words can be transformed into each other by one swap exactly when they differ in exactly two positions. If the words are abc and acb, swapping the last two positions of abc produces acb. If the words are abc and bca, all three positions differ, so one swap cannot transform one into the other.

The input contains one integer (N), followed by the (N) words. The output is the maximum number of words that can remain after choosing a swap-free subset. The original contest constraints give (1 \le N \le 500), and every word uses distinct lowercase English letters, so its length is at most 26. The Codeforces archive gives a 1 second time limit and 512 MB memory limit.

The bound (N \le 500) rules out exponential subset enumeration immediately. Even (2^{500}) subsets are far beyond anything a program can inspect. On the other hand, cubic algorithms are entirely reasonable for 500 vertices, since (500^3 = 125{,}000{,}000). The word length is at most 26, so comparing two words character by character is cheap. The real challenge is not detecting whether two words are connected, but recognizing the graph structure that makes maximum independent set tractable.

There are several edge cases that can make a careless implementation fail. With one word, there is nothing to conflict with, so the answer is 1.

1
a

The correct output is 1. An implementation that assumes every word has at least two positions and tries to generate a swap can accidentally access an invalid position.

A second edge case is when two words differ by exactly one swap.

2
ab
ba

The correct output is 1. The two words are connected by a swap, so they cannot both be selected. A program that checks whether the words are different rather than checking whether one swap connects them would incorrectly return 2.

A third edge case is when two words are anagrams but require more than one swap.

3
abc
bca
cab

The correct output is 3. Every pair differs in all three positions, so no single swap transforms one word into another. A careless solution that treats every pair of anagrams as a conflict would incorrectly discard some words.

The condition that letters are distinct also matters. There is no valid word such as aab, so swapping two equal letters never needs special handling. This restriction is exactly what lets us characterize a one-swap transformation by a Hamming distance of two. The statement explicitly guarantees distinct letters and unique words.

Approaches

The direct brute-force approach is to consider every subset of the (N) words and check whether it is swap-free. For a subset, we can compare every pair of selected words and reject the subset if some pair differs in exactly two positions. This is correct because the definition of a swap-free set is precisely that no selected pair has such a relationship.

The problem is the number of subsets. There are (2^N) possible subsets, and checking one subset can require (O(N^2)) pair comparisons. In the worst case this gives (O(2^N N^2)) work. For (N=500), the subset count alone is about (3.27 \times 10^{150}), so this approach is not remotely viable.

The useful observation is to stop thinking about words as strings and instead make them vertices of a graph. Connect two vertices when one word can be obtained from the other with one swap. Then a swap-free set is exactly an independent set of this graph, so the problem becomes finding a maximum independent set.

Maximum independent set is generally difficult, but this particular graph has additional structure. Every word is a permutation of the same set of distinct letters. Give each permutation a parity, even or odd, according to the parity of its inversion count. Swapping two positions changes the permutation by one transposition, and every transposition flips the parity. Consequently, every edge connects an even permutation to an odd permutation.

The graph is thus bipartite. This is the key reduction. For a bipartite graph, König's theorem says that the size of a minimum vertex cover equals the size of a maximum matching. The complement of a minimum vertex cover is an independent set, so

N-\text{minimum vertex cover}

N-\text{maximum matching}. ]

The official solution outline uses exactly this reduction and observes that an (O(N^3)) bipartite matching algorithm is sufficient for (N \le 500).

We still need to build the graph. Since every word has length at most 26 and there are only 500 words, comparing every pair and counting differing positions is easily fast enough. If exactly two positions differ, the two words are connected by one swap.

For the matching itself, a straightforward Kuhn algorithm is (O(N^3)) in the worst case here, but Python benefits from using Hopcroft-Karp. Its worst-case complexity is (O(E\sqrt N)), where (E) is the number of swap edges. Since (E=O(N^2)), the matching phase is (O(N^{2.5})) in the worst case.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	(O(2^N N^2))	(O(N^2))	Too slow
Optimal	(O(N^2L + E\sqrt N)), (L\le26)	(O(N^2))	Accepted

Algorithm Walkthrough

Read the (N) words and store them. Since every word is an anagram of every other word and all words are distinct, every vertex represents a different permutation of the same letters.
Compute the parity of every word. Map the letters to their ranks in a fixed order, then count inversions in the resulting sequence. An even inversion count puts the word on the left side of the bipartite graph, while an odd inversion count puts it on the right.

The particular reference order does not matter. Changing the reference only changes how the two parity classes are named. What matters is that one transposition always flips parity. 3. Compare every pair of words. Count the positions where their characters differ. If exactly two positions differ, add an edge between the corresponding vertices.

Because the words are anagrams with distinct letters, two positions differing is both necessary and sufficient for a single swap. The two different characters must simply be exchanged. 4. Store only edges from the even-parity words to the odd-parity words. There cannot be an edge between two words of the same parity, because a single swap changes parity. 5. Run Hopcroft-Karp to find a maximum matching in this bipartite graph. The matching size is the minimum number of vertices that must be removed to eliminate every swap conflict. 6. Return (N) minus the matching size. König's theorem gives the equality between maximum matching and minimum vertex cover, while the complement of a minimum vertex cover is a maximum independent set.

Why it works

The invariant behind the reduction is permutation parity. Every edge represents exactly one transposition, and every transposition changes inversion parity, so every edge crosses from one parity class to the other. The conflict graph is consequently bipartite.

A valid answer is an independent set because no two selected words may be connected by a swap edge. In any bipartite graph, the largest independent set has size (N-\tau), where (\tau) is the minimum vertex-cover size. König's theorem gives (\tau=M), where (M) is the maximum matching size. Thus the required answer is exactly (N-M), which is what the algorithm computes.

Python Solution

import sys
from collections import deque

input = sys.stdin.readline

def inversion_parity(word):
    # The alphabet itself can be used as the fixed reference order.
    # Since every word contains distinct lowercase letters, this is
    # exactly the parity of the corresponding permutation.
    a = [ord(c) - ord('a') for c in word]
    parity = 0

    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] > a[j]:
                parity ^= 1

    return parity

def hopcroft_karp(graph, left_size, right_size):
    pair_left = [-1] * left_size
    pair_right = [-1] * right_size
    dist = [-1] * left_size

    def bfs():
        q = deque()

        for u in range(left_size):
            if pair_left[u] == -1:
                dist[u] = 0
                q.append(u)
            else:
                dist[u] = -1

        found = False

        while q:
            u = q.popleft()

            for v in graph[u]:
                u2 = pair_right[v]

                if u2 == -1:
                    found = True
                elif dist[u2] == -1:
                    dist[u2] = dist[u] + 1
                    q.append(u2)

        return found

    def dfs(u):
        for v in graph[u]:
            u2 = pair_right[v]

            if u2 == -1 or (
                dist[u2] == dist[u] + 1 and dfs(u2)
            ):
                pair_left[u] = v
                pair_right[v] = u
                return True

        dist[u] = -1
        return False

    matching = 0

    while bfs():
        for u in range(left_size):
            if pair_left[u] == -1 and dfs(u):
                matching += 1

    return matching

def solve():
    n = int(input())
    words = [input().strip() for _ in range(n)]

    parity = [inversion_parity(word) for word in words]

    left = []
    right = []

    for i in range(n):
        if parity[i] == 0:
            left.append(i)
        else:
            right.append(i)

    right_id = [-1] * n
    for j, v in enumerate(right):
        right_id[v] = j

    graph = [[] for _ in range(len(left))]

    for li, u in enumerate(left):
        wu = words[u]

        for v in right:
            wv = words[v]
            different = 0

            for a, b in zip(wu, wv):
                if a != b:
                    different += 1
                    if different > 2:
                        break

            if different == 2:
                graph[li].append(right_id[v])

    matching = hopcroft_karp(graph, len(left), len(right))
    print(n - matching)

if __name__ == "__main__":
    solve()

The input phase simply stores the words because there is only one test case. The parity function converts each word into its sequence of alphabet ranks and counts inversions. Since the word has distinct letters, every pair contributes either zero or one inversion, so the parity calculation is straightforward and takes (O(L^2)) time for a word.

The two parity classes are then converted into compact left and right vertex indices. This makes the matching arrays smaller and avoids carrying the original word indices through the Hopcroft-Karp implementation.

The graph construction compares only opposite-parity words. For every pair, the loop counts differing positions and stops as soon as the count exceeds two. This early exit is not necessary for correctness, but it avoids unnecessary character comparisons for unrelated words.

The matching code uses pair_left and pair_right to represent the current matching. The BFS phase builds layers of alternating paths, while DFS searches only along those layers. Several shortest augmenting paths can be found during one BFS phase, which is what gives Hopcroft-Karp its (O(E\sqrt N)) bound.

There is no integer-overflow issue in Python. The main implementation detail to keep straight is the indexing: graph is indexed by positions in left, while its neighbors are positions in right. The original word indices are translated through right_id.

Worked Examples

Sample 1

The six words are all permutations of abc. Their parity classes are determined by their inversion counts.

Word	Inversion parity	Left/Right	Swap edges considered
`abc`	0	Left	`acb`, `cba`, `bac`
`acb`	1	Right	`abc`, `cab`, `bca`
`cab`	0	Left	`acb`, `cba`, `bca`
`cba`	1	Right	`abc`, `cab`, `bac`
`bac`	1	Right	`abc`, `cab`, `bca`
`bca`	0	Left	`acb`, `cba`, `bac`

The conflict graph is (K_{3,3}), so its maximum matching has size 3. The algorithm returns (6-3=3).

6
abc
acb
cab
cba
bac
bca

This example demonstrates the full reduction. Although the original problem asks for a largest collection of words, the answer is obtained entirely from the matching size of the swap graph.

Sample 2

For the eleven words based on alerts, the graph is again split by permutation parity. Only pairs at Hamming distance two receive edges.

Stage	Number of words	Result
Input	11	11 vertices
Even parity	6	Left side
Odd parity	5	Right side
Maximum matching	3	3 conflicts can be covered
Maximum swap-free set	8	(11-3=8)

11
alerts
alters
artels
estral
laster
ratels
salter
slater
staler
stelar
talers

The trace demonstrates that the graph does not have to contain every possible permutation. We only build edges among the supplied words, and the matching operates on this induced bipartite graph. The official statement lists this sample with answer 8.

Complexity Analysis

Measure	Complexity	Explanation
Time	(O(N^2L + E\sqrt N))	(N^2) word pairs are compared in (O(L)), followed by Hopcroft-Karp
Space	(O(N^2))	The conflict graph can contain (O(N^2)) edges

Here (L\le26) because a word contains no repeated lowercase letter, and (E\le N^2/4) for a bipartite graph. With (N\le500), graph construction is small, and Hopcroft-Karp comfortably handles the possible number of edges. The official solution accepts an (O(N^3)) matching algorithm as sufficient for these constraints, so the Python implementation has additional asymptotic margin in the matching phase.

Test Cases

# The production solution can be tested by moving solve() into this file
# and replacing its stdin/stdout handling with the helper below.

import io
import sys
from collections import deque
from itertools import permutations

def inversion_parity(word):
    a = [ord(c) - ord('a') for c in word]
    parity = 0

    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] > a[j]:
                parity ^= 1

    return parity

def hopcroft_karp(graph, left_size, right_size):
    pair_left = [-1] * left_size
    pair_right = [-1] * right_size
    dist = [-1] * left_size

    def bfs():
        q = deque()

        for u in range(left_size):
            if pair_left[u] == -1:
                dist[u] = 0
                q.append(u)
            else:
                dist[u] = -1

        found = False

        while q:
            u = q.popleft()

            for v in graph[u]:
                u2 = pair_right[v]

                if u2 == -1:
                    found = True
                elif dist[u2] == -1:
                    dist[u2] = dist[u] + 1
                    q.append(u2)

        return found

    def dfs(u):
        for v in graph[u]:
            u2 = pair_right[v]

            if u2 == -1 or (
                dist[u2] == dist[u] + 1 and dfs(u2)
            ):
                pair_left[u] = v
                pair_right[v] = u
                return True

        dist[u] = -1
        return False

    matching = 0

    while bfs():
        for u in range(left_size):
            if pair_left[u] == -1 and dfs(u):
                matching += 1

    return matching

def solution(inp):
    data = inp.split()
    n = int(data[0])
    words = data[1:1 + n]

    parity = [inversion_parity(w) for w in words]

    left = [i for i in range(n) if parity[i] == 0]
    right = [i for i in range(n) if parity[i] == 1]

    right_id = [-1] * n
    for j, v in enumerate(right):
        right_id[v] = j

    graph = [[] for _ in left]

    for li, u in enumerate(left):
        for v in right:
            different = 0

            for a, b in zip(words[u], words[v]):
                if a != b:
                    different += 1
                    if different > 2:
                        break

            if different == 2:
                graph[li].append(right_id[v])

    matching = hopcroft_karp(graph, len(left), len(right))
    return str(n - matching) + "\n"

def run(inp: str) -> str:
    return solution(inp)

# Provided sample 1
assert run(
    """6
abc
acb
cab
cba
bac
bca
"""
) == "3\n", "sample 1"

# Provided sample 2
assert run(
    """11
alerts
alters
artels
estral
laster
ratels
salter
slater
staler
stelar
talers
"""
) == "8\n", "sample 2"

# Provided sample 3
assert run(
    """6
ates
east
eats
etas
sate
teas
"""
) == "4\n", "sample 3"

# Minimum-size and all-equal-value analogue.
# A word with one distinct lowercase letter has only one possible form.
assert run(
    """1
a
"""
) == "1\n", "single word"

# Two words connected by exactly one swap.
assert run(
    """2
ab
ba
"""
) == "1\n", "single conflict"

# Three words that are all anagrams but no pair is one swap apart.
assert run(
    """3
abc
bca
cab
"""
) == "3\n", "no conflict edges"

# Maximum-size case.
# The first 500 even permutations of eight letters all have the same parity,
# so no two of them can be connected by one swap.
even_words = []

for p in permutations("abcdefgh"):
    w = "".join(p)
    if inversion_parity(w) == 0:
        even_words.append(w)
        if len(even_words) == 500:
            break

max_case = "500\n" + "\n".join(even_words) + "\n"
assert run(max_case) == "500\n", "maximum-size independent set"

Test input	Expected output	What it validates
`1 / a`	`1`	Minimum (N), minimum word length, no possible swap
`2 / ab, ba`	`1`	Direct one-swap conflict and matching of size 1
`3 / abc, bca, cab`	`3`	Anagrams that cannot be connected by one swap
500 even permutations of `abcdefgh`	`500`	Maximum (N), dense input size, and the parity invariant
Sample 1	`3`	Complete (S_3) permutation structure
Sample 2	`8`	Partial permutation graph
Sample 3	`4`	Another partial graph with the same letter set size

Edge Cases

For a single word, there are no pairs to compare, so the graph has one isolated vertex and the maximum matching has size zero.

1
a

The algorithm puts a into one parity class, creates no edges, and computes (1-0=1). The result is correct even though the word has no pair of positions that could be swapped.

For two words that are direct swaps, the graph contains one edge.

2
ab
ba

ab has even parity and ba has odd parity. Their Hamming distance is two, so the algorithm creates one bipartite edge. The maximum matching has size one, giving (2-1=1). This catches implementations that accidentally count an arbitrary pair of different words as compatible.

For words that are anagrams but require more than one swap, no edge is created.

3
abc
bca
cab

abc and bca differ in all three positions, as do the other pairs. The graph therefore has three isolated vertices. Its maximum matching is zero, so the answer is (3). This is why checking anagram equality alone is insufficient.

The parity boundary is also important. Two words connected by a single swap must have opposite inversion parity. In the maximum-size test, all 500 words are deliberately chosen from the same parity class. They may look highly different from one another, but no pair can be related by one transposition. The graph has no edges and the answer is all 500 words. This directly tests the structural observation used to turn the original optimization problem into bipartite matching.

The editorial is ready to use as a submission-quality explanation. If you want, I can also produce a shorter Codeforces-style version that keeps the same proof but is optimized for contest readers.

CF 102423D - Swap Free