{"problem":{"name":"D. Two Strings Swaps","description":{"content":"You are given two strings $a$ and $b$ consisting of lowercase English letters, both of length $n$. The characters of both strings have indices from $1$ to $n$, inclusive. You are allowed to do the fo","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1006D"},"statements":[{"statement_type":"Markdown","content":"You are given two strings $a$ and $b$ consisting of lowercase English letters, both of length $n$. The characters of both strings have indices from $1$ to $n$, inclusive.\n\nYou are allowed to do the following _changes_:\n\n*   Choose any index $i$ ($1 \\le i \\le n$) and swap characters $a_i$ and $b_i$;\n*   Choose any index $i$ ($1 \\le i \\le n$) and swap characters $a_i$ and $a_{n - i + 1}$;\n*   Choose any index $i$ ($1 \\le i \\le n$) and swap characters $b_i$ and $b_{n - i + 1}$.\n\nNote that if $n$ is odd, you are formally allowed to swap $a_{\\lceil\\frac{n}{2}\\rceil}$ with $a_{\\lceil\\frac{n}{2}\\rceil}$ (and the same with the string $b$) but this move is useless. Also you can swap two equal characters but this operation is useless as well.\n\nYou have to make these strings equal by applying any number of _changes_ described above, in any order. But it is obvious that it may be impossible to make two strings equal by these swaps.\n\nIn one _preprocess move_ you can replace a character in $a$ with another character. In other words, in a single _preprocess move_ you can choose any index $i$ ($1 \\le i \\le n$), any character $c$ and set $a_i := c$.\n\nYour task is to find the minimum number of _preprocess moves_ to apply in such a way that after them you can make strings $a$ and $b$ equal by applying some number of _changes_ described in the list above.\n\nNote that the number of _changes_ you make after the _preprocess moves_ does not matter. Also note that you cannot apply _preprocess moves_ to the string $b$ or make any _preprocess moves_ after the first _change_ is made.\n\n## Input\n\nThe first line of the input contains one integer $n$ ($1 \\le n \\le 10^5$) — the length of strings $a$ and $b$.\n\nThe second line contains the string $a$ consisting of exactly $n$ lowercase English letters.\n\nThe third line contains the string $b$ consisting of exactly $n$ lowercase English letters.\n\n## Output\n\nPrint a single integer — the minimum number of _preprocess moves_ to apply before _changes_, so that it is possible to make the string $a$ equal to string $b$ with a sequence of _changes_ from the list above.\n\n[samples]\n\n## Note\n\nIn the first example _preprocess moves_ are as follows: $a_1 := $ '_b_', $a_3 := $ '_c_', $a_4 := $ '_a_' and $a_5:=$'_b_'. Afterwards, $a = $ \"_bbcabba_\". Then we can obtain equal strings by the following sequence of _changes_: $swap(a_2, b_2)$ and $swap(a_2, a_6)$. There is no way to use fewer than $4$ _preprocess moves_ before a sequence of _changes_ to make string equal, so the answer in this example is $4$.\n\nIn the second example no _preprocess moves_ are required. We can use the following sequence of _changes_ to make $a$ and $b$ equal: $swap(b_1, b_5)$, $swap(a_2, a_4)$.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"给你两个由小写英文字母组成的字符串 $a$ 和 $b$，长度均为 $n$。两个字符串的字符下标均为 $1$ 到 $n$。 \n\n你可以进行以下 _操作_： \n\n注意，如果 $n$ 为奇数，你形式上可以交换 $a_{\\lceil \\frac{n}{2} \\rceil}$ 与 $a_{\\lceil \\frac{n}{2} \\rceil}$（对字符串 $b$ 同理），但这种操作是无用的。同样，交换两个相同字符的操作也是无用的。\n\n你需要通过应用任意数量的上述 _操作_（顺序任意），使两个字符串相等。但显然，仅通过这些交换可能无法使两个字符串相等。\n\n在一次 _预处理操作_ 中，你可以将 $a$ 中的一个字符替换为另一个字符。换句话说，在单次 _预处理操作_ 中，你可以选择任意下标 $i$（$1 \\lt.eq i \\lt.eq n$）和任意字符 $c$，并将 $a_i := c$。\n\n你的任务是找到最少的 _预处理操作_ 数量，使得在应用这些操作后，你可以通过上述列表中描述的若干次 _操作_ 使字符串 $a$ 和 $b$ 相等。\n\n注意，你在 _预处理操作_ 之后进行的 _操作_ 数量无关紧要。同时，你不能对字符串 $b$ 应用 _预处理操作_，也不能在第一次 _操作_ 之后再进行任何 _预处理操作_。\n\n输入的第一行包含一个整数 $n$（$1 \\lt.eq n \\lt.eq 10^5$）——字符串 $a$ 和 $b$ 的长度。\n\n第二行包含由恰好 $n$ 个小写英文字母组成的字符串 $a$。\n\n第三行包含由恰好 $n$ 个小写英文字母组成的字符串 $b$。\n\n输出一个整数——在进行 _操作_ 之前，最少需要应用的 _预处理操作_ 数量，使得可以通过上述列表中的 _操作_ 序列使字符串 $a$ 与字符串 $b$ 相等。\n\n在第一个例子中，_预处理操作_ 如下：$a_1 := $'_b_'，$a_3 := $'_c_'，$a_4 := $'_a_'，$a_5 := $'_b_'。之后，$a =$\"_bbcabba_\"。然后我们可以通过以下 _操作_ 序列得到相等的字符串：$swap(a_2, b_2)$ 和 $swap(a_2, a_6)$。在进行 _操作_ 之前，无法用少于 $4$ 次 _预处理操作_ 使字符串相等，因此该例子的答案为 $4$。\n\n在第二个例子中，不需要任何 _预处理操作_。我们可以通过以下 _操作_ 序列使 $a$ 和 $b$ 相等：$swap(b_1, b_5)$，$swap(a_2, a_4)$。\n\n## Input\n\n输入的第一行包含一个整数 $n$（$1 \\lt.eq n \\lt.eq 10^5$）——字符串 $a$ 和 $b$ 的长度。第二行包含由恰好 $n$ 个小写英文字母组成的字符串 $a$。第三行包含由恰好 $n$ 个小写英文字母组成的字符串 $b$。\n\n## Output\n\n输出一个整数——在进行 _操作_ 之前，最少需要应用的 _预处理操作_ 数量，使得可以通过上述列表中的 _操作_ 序列使字符串 $a$ 与字符串 $b$ 相等。\n\n[samples]\n\n## Note\n\n在第一个例子中，_预处理操作_ 如下：$a_1 := $'_b_'，$a_3 := $'_c_'，$a_4 := $'_a_'，$a_5 := $'_b_'。之后，$a =$\"_bbcabba_\"。然后我们可以通过以下 _操作_ 序列得到相等的字符串：$swap(a_2, b_2)$ 和 $swap(a_2, a_6)$。在进行 _操作_ 之前，无法用少于 $4$ 次 _预处理操作_ 使字符串相等，因此该例子的答案为 $4$。在第二个例子中，不需要任何 _预处理操作_。我们可以通过以下 _操作_ 序列使 $a$ 和 $b$ 相等：$swap(b_1, b_5)$，$swap(a_2, a_4)$。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of strings $ a $ and $ b $.  \nLet $ a = (a_1, a_2, \\dots, a_n) $, $ b = (b_1, b_2, \\dots, b_n) $ be strings over the alphabet $ \\Sigma = \\{ \\text{a}, \\text{b}, \\dots, \\text{z} \\} $.\n\n**Allowed Changes**  \nYou may perform any number of swaps:  \n- Swap $ a_i \\leftrightarrow a_j $ for any $ i, j \\in \\{1, \\dots, n\\} $,  \n- Swap $ b_i \\leftrightarrow b_j $ for any $ i, j \\in \\{1, \\dots, n\\} $.  \n\n(Note: Swaps within $ a $ and within $ b $ are unrestricted; no swaps between $ a $ and $ b $ are allowed.)\n\n**Preprocess Move**  \nYou may replace any character $ a_i $ with any character $ c \\in \\Sigma $, for any index $ i \\in \\{1, \\dots, n\\} $.  \nThis can be done only once per position, before any swaps, and only on string $ a $.\n\n**Objective**  \nFind the minimum number of preprocess moves required on $ a $ such that, after these replacements, there exists a sequence of allowed swaps (within $ a $ and within $ b $) that makes $ a = b $.\n\n---\n\n**Constraints**  \n1. $ 1 \\le n \\le 10^5 $  \n2. $ a_i, b_i \\in \\Sigma $ for all $ i \\in \\{1, \\dots, n\\} $\n\n---\n\n**Key Insight**  \nAfter preprocess moves, we can rearrange the characters within $ a $ arbitrarily (via swaps), and similarly within $ b $.  \nThus, after preprocess moves, the multiset of characters in $ a $ must equal the multiset of characters in $ b $, because only internal rearrangements are allowed.\n\nLet $ \\text{freq}_a(c) $ and $ \\text{freq}_b(c) $ denote the frequency of character $ c $ in $ a $ and $ b $, respectively.\n\nWe are allowed to change characters in $ a $ arbitrarily. We wish to minimize the number of such changes so that:\n\n$$\n\\text{freq}_a'(c) = \\text{freq}_b(c) \\quad \\forall c \\in \\Sigma\n$$\n\nwhere $ a' $ is the modified version of $ a $ after preprocess moves.\n\nThe minimal number of preprocess moves is the total number of character \"excesses\" in $ a $ relative to $ b $, which is:\n\n$$\n\\frac{1}{2} \\sum_{c \\in \\Sigma} \\left| \\text{freq}_a(c) - \\text{freq}_b(c) \\right|\n$$\n\nBut note: each preprocess move changes one character in $ a $, and can reduce the difference for two characters: decrease one character’s excess and increase another’s deficit.\n\nActually, the minimal number of preprocess moves is:\n\n$$\n\\sum_{c \\in \\Sigma} \\max(0, \\text{freq}_a(c) - \\text{freq}_b(c))\n$$\n\nBecause:  \n- We can only change characters in $ a $.  \n- For each character $ c $, if $ a $ has more of $ c $ than $ b $, we must change the excess $ \\text{freq}_a(c) - \\text{freq}_b(c) $ occurrences of $ c $ into other characters.  \n- The total number of such excesses equals the total number of \"missing\" characters in $ a $ (since total length is fixed), so summing the positive differences gives the minimal number of changes.\n\nAlternatively, since $ \\sum_c \\text{freq}_a(c) = \\sum_c \\text{freq}_b(c) = n $, we have:\n\n$$\n\\sum_{c \\in \\Sigma} \\max(0, \\text{freq}_a(c) - \\text{freq}_b(c)) = \\sum_{c \\in \\Sigma} \\max(0, \\text{freq}_b(c) - \\text{freq}_a(c))\n$$\n\nSo the minimal number of preprocess moves is:\n\n$$\n\\sum_{c \\in \\Sigma} \\max(0, \\text{freq}_a(c) - \\text{freq}_b(c))\n$$\n\n---\n\n**Final Formal Statement**\n\n**Objective**  \nCompute:\n$$\n\\min \\text{preprocess moves} = \\sum_{c \\in \\Sigma} \\max\\left(0, \\text{freq}_a(c) - \\text{freq}_b(c)\\right)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1006D","tags":["implementation"],"sample_group":[["7\nabacaba\nbacabaa","4"],["5\nzcabd\ndbacz","0"]],"created_at":"2026-03-03 11:00:39"}}