MCC 2025 P4: Word Distance

Word Distance

Problem Statement

You are given $N$ words. Each word is a string of length $M$ consisting only of lowercase letters.

The distance between 2 words is defined as the minimum number of letters that need to be replaced in either word so that the two words become anagrams¹ of each other.

You are given a task to construct a word of length $M$ that minimizes the sum of distances to all $N$ given words. If there are multiple such words, output the lexicographically smallest² one.

Note:

¹ A word is an anagram of another if it can be formed by rearranging the letters of the other word. For example, `baab` is an anagram of `aabb`, but not of `baaa` because `aabb` can be rearranged into `baab` by swapping the first and third letter, but there is no rearrangement of `baaa` that forms `baab`.

² A string $s_1$ is lexicographically smaller than a string $s_2$ of the same length if and only if in the first position where $s_1$ and $s_2$ differ, the string $s_1$ has a letter that appears earlier in the alphabet than the corresponding letter in $s_2$. For example, `aabc` is lexicographically smaller than `abaa` because the first position where both strings differ is the second position and letter `a` appears earlier in alphabet than letter `b`.

Input Format

The first line contains two space-separated integers, $N$ and $M$.

Each of the next $N$ lines contains a string of length $M$.

Output Format

Output the lexicographically smallest word of length $M$ with the minimum sum of distance to all the words.

Constraints

For all tasks:

• $1 \leq N,M \leq 10\,000$.
• $1 \leq N \times M \leq 100\,000$.

• The words only consist of lowercase letters.

• Task 1 (10 points): $N = 4, M = 4$
• Task 2 (10 points): $N = 4, M = 4$
• Task 3 (10 points): $N = 100, M = 4$
• Task 4 (10 points): All the given words are anagrams.
• Task 5 (10 points): The words consist of only a and b.
• Task 6 (10 points): The words consist of only a and b.
• Task 7 (10 points): The words consist of only a and b.
• Task 8 (10 points): No additional constraints
• Task 9 (10 points): No additional constraints
• Task 10 (10 points): No additional constraints

Sample Input

5 3
adb
dez
zaf
aed
wxy

Sample Output

ade

Sample Explanation

The distance of the word ade to each of the given words is 1, 1, 2, 0 and 3, respectively, as shown.

• Distance between ade and adb is 1: They only differ at the last letter so you can replace the last letter of either word to make them the same (which are also anagrams).
• Distance between ade and dez is 1: Replace the word ade to zde (i.e. replace the letter a to z) to make them anagrams. We can rearrange zde to dez by rearranging the first, second and third letters to the third, first and second positions, respectively.
• Distance between ade and zaf is 2: Replace the word ade to azf (i.e. replace the letter d to z and replace the letter e to f) to make them anagrams. Replacing 2 letters is necessary because replacing any one letter only would not make them anagrams.
• Distance between ade and aed is 0: They are anagrams.
• Distance between ade and wxy is 3: Replace the entire word ade to wxy to make them anagrams. Since none of the letters are in common so it is necessary to change all the letters in the word.

The total distance is $1 + 1 + 2 + 0 + 3 = 7$ and it can be proven that this is the minimum possible sum of distance. Do note that aed and adz are also words with a minimum sum of distance to all the given words. However, they are NOT the answer to this problem because

• ade is lexicographically smaller than aed because at the second position (i.e. the first position where both string differs), letter d appears earlier in alphabet than letter e.
• ade is lexicographically smaller than adz because at the third position, letter e appears earlier in alphabet than letter z.

Jarak Perkataan

Pernyataan Masalah

Anda diberikan $N$ perkataan. Setiap perkataan ialah rentetan (string) sepanjang $M$ yang hanya terdiri daripada huruf kecil.

Jarak antara dua perkataan ditakrifkan sebagai bilangan huruf minimum yang perlu digantikan dalam salah satu perkataan supaya kedua-duanya menjadi anagram¹ antara satu sama lain.

Tugas anda ialah untuk membina satu perkataan sepanjang $M$ yang meminimumkan jumlah jarak kepada semua $N$ perkataan yang diberikan. Jika terdapat lebih daripada satu perkataan yang mempunyai jumlah jarak minimum, keluarkan perkataan yang terkecil dari segi leksikografi².

Nota:

¹ Sebuah perkataan ialah anagram kepada perkataan lain jika ia boleh dibentuk dengan menyusun semula huruf-huruf perkataan tersebut. Contohnya, `baab` ialah anagram kepada `aabb`, tetapi bukan kepada `baaa` kerana `aabb` boleh disusun semula kepada `baab` dengan menukarkan huruf pertama dan ketiga, tetapi tiada susunan semula untuk `baaa` yang membentuk `baab`.

² Rentetan $s_1$ dikatakan lebih kecil secara leksikografi daripada $s_2$ (yang sama panjang) jika dan hanya jika pada kedudukan pertama yang $s_1$ dan $s_2$ berbeza, rentetan $s_1$ mempunyai huruf yang muncul lebih awal dalam susunan abjad berbanding huruf pada kedudukan yang sama dalam $s_2$. Contohnya, `aabc` ialah lebih kecil secara leksikografi daripada `abaa` kerana posisi pertama yang kedua-dua rentetan berbeza ialah posisi kedua dan huruf `a` muncul lebih awal dalam sususan abjad daripada huruf `b`.

Format Input

Baris pertama mengandungi dua integer yang dipisahkan oleh ruang, $N$ dan $M$.

Setiap satu daripada $N$ baris seterusnya mengandungi satu rentetan sepanjang $M$.

Format Output

Keluarkan satu perkataan sepanjang $M$ yang mempunyai jumlah jarak minimum terhadap semua perkataan yang diberikan, dan juga merupakan yang terkecil secara leksikografi antara semua pilihan yang mungkin.

Kekangan

Untuk semua tugasan:

• $1 \leq N, M \leq 10\,000$.
• $1 \leq N \times M \leq 100\,000$.

• Semua perkataan hanya mengandungi huruf kecil.

• Tugasan 1 (10 markah): $N = 4, M = 4$
• Tugasan 2 (10 markah): $N = 4, M = 4$
• Tugasan 3 (10 markah): $N = 100, M = 4$
• Tugasan 4 (10 markah): Semua perkataan yang diberikan ialah anagram.
• Tugasan 5 (10 markah): Semua perkataan hanya terdiri daripada huruf a dan b.
• Tugasan 6 (10 markah): Semua perkataan hanya terdiri daripada huruf a dan b.
• Tugasan 7 (10 markah): Semua perkataan hanya terdiri daripada huruf a dan b.
• Tugasan 8 (10 markah): Tiada kekangan tambahan.
• Tugasan 9 (10 markah): Tiada kekangan tambahan.
• Tugasan 10 (10 markah): Tiada kekangan tambahan.

Contoh Input

5 3
adb
dez
zaf
aed
wxy

Contoh Output

ade

Penjelasan Contoh

Jarak antara perkataan ‘ade’ dan setiap perkataan yang diberikan adalah masing-masing 1, 1, 2, 0, dan 3 seperti berikut:

• Jarak antara ade dan adb ialah 1: Hanya berbeza pada huruf terakhir jadi anda boleh tukarkan huruf terakhir bagi mana-mana perkataan untuk menjadikan mereka sama (yang juga Adalah anagram).
• Jarak antara ade dan dez ialah 1: Tukar ade menjadi zde (tukarkan huruf a kepada z) untuk menjadikan mereka anagram. Kita boleh susun semula zde kepada dez dengan Menyusun semula huruf-huruf pertama, kedua, dan ketiga masing-masing kepada posisi-posisi ketiga, pertama, dan kedua.
• Jarak antara ade dan zaf ialah 2: Tukar ade menjadi azf (gantikan d dengan z dan gantikan huruf e dengan f) untuk menjadikan mereka anagram. Menggantikan 2 huruf Adalah perlu kerana menukarkan hanya satu huruf tidak akan menjadikan mereka anagram.
• Jarak antara ade dan aed ialah 0: Kedua-duanya sudah merupakan anagram.
• Jarak antara ade dan wxy ialah 3: Gantikan keseluruan perkataan ade dengan wxy. Tiada huruf yang sama, maka semua huruf perlu digantikan.

Jumlah jarak ialah 1 + 1 + 2 + 0 + 3 = 7, dan boleh dibuktikan yang ini merupakan jumlah minimum yang mungkin. Perkataan aed dan adz juga mempunyai jumlah jarak minimum yang sama kepada kesemua perkataan yang diberikan. Tetapi mereka BUKAN jawapan akhir kerana:

• ‘ade’ lebih kecil secara leksikografi daripada ‘aed’ (huruf kedua ‘d’ muncul lebih awal daripada ‘e’).
• ‘ade’ lebih kecil secara leksikografi daripada ‘adz’ (huruf ketiga ‘e’ muncul lebih awal daripada ‘z’).

单词距离

题目描述

给定 $N$ 个单词。每个词都是由 $M$ 个小写英文字幕组成的字符串。

定义两个词的距离为使两个单词变为互为变位词¹（anagram）所需替换的最少字母数。

你的任务是构造一个长度为 $M$ 的单词且与所有 $N$ 个给定的词的距离的和是最小的。如果有多个符合条件的单词，输出字典序² 最小的那个。

注意:

¹ 若一个单词可以通过重新排列另一个单词中的字母得到，则称这两个单词互为变位词（anagram）。例如，`baab` 是 `aabb` 的变位词，但不是 `baaa` 的变位词，因为 `aabb` 通过交换第一个和第三个字母即可得到 `baab`，而无论如何重新排列 `baaa` 都无法得到 `baab`。

² 若两个等长字符串 $s_1$ 和 $s_2$ 在第一个不同的位置上，$s_1$​ 的该位置字母在字母表中比 $s_2$​ 的对应字母更靠前，则称 $s_1$​ 字典序小于 $s_2$​。例如，`aabc` 的字典序小于 `abaa`，因为它们第一个不同的位置是第二个字符，而字母 `a` 在字母表中比 `b` 更靠前。

输入格式

第一行含有两个整数 $N$ 和 $M$。

接下来的 $N$ 行含有一个长度为 $M$ 的字符串。

输出格式

输出一个长度为 $M$ 的字符串表示符合距离总和最小的字典序最小的单词。

约束

对于每项任务:

• $1 \leq N,M \leq 10\,000$。
• $1 \leq N \times M \leq 100\,000$。

• 单词只由小写英文字母组成。

• 任务 1（10 分）：$N = 4, M = 4$
• 任务 2（10 分）：$N = 4, M = 4$
• 任务 3（10 分）：$N = 100, M = 4$
• 任务 4（10 分）：给定的单词都互为变位词。
• 任务 5（10 分）：单词只由 a 和 b 组成。
• 任务 6（10 分）：单词只由 a 和 b 组成。
• 任务 7（10 分）：单词只由 a 和 b 组成。
• 任务 8（10 分）：无额外约束。
• 任务 9（10 分）：无额外约束。
• 任务 10（10 分）：无额外约束。

样例输入

5 3
adb
dez
zaf
aed
wxy

样例输出

ade

样例解释

ade 和其他词的距离分别是 1、1、2、0和3，如下：

• ade 和 adb 的距离是 1：它们只在最后一个字母不同，因此只需将任意一个单词的最后一个字母替换为另一个即可使两个单词相同（也即互为变位词）。
• ade 和 dez 的距离是 1：将 ade 替换 zde（即替换其字母 a 至 z）使得它们是互为变位词。我们可以通过将第一个、第二个和第三个字母分别移动到第三、第一和第二个位置，将 zde 重新排列为 dez。
• ade 和 zaf 的距离是 2：将 ade 替换 azf（即替换其字母 d 至 z 和字母 e 至 f）使得它们是互为变位词。替换两个字母是必要的因为仅替换任意一个字母不能湿它们互为变位词。
• ade 和 aed 的距离是 0：它们已经是互为变位词。
• ade 和 wxy 的距离是 3：将整个单词 ade 替换成 wxy 使得它们是互为变位词。由于它们没有任何共同的字母，所以替换其中一个词的所有字母是必要的。

距离的总和是 $1 + 1 + 2 + 0 + 3 = 7$ 并且可以证明，这样得到的距离和是最小的。注意 aed 和 adz 也是最小总距离的单词但是它们不是答案因为

• ade 的字典序比 aed 小，因为在第二个位置（即两个字符串第一个不同的位置），字母 d 在字母表中比字母 e 更靠前。
• ade 的字典序比 adz 小，因为在第三个位置，字母 e 在字母表中比字母 z 更靠前。