Two relay towers, Tower A and Tower B, each keep a log of the broadcast band used at every one of their synchronized time slots. Every slot's band is written as a single lowercase letter from 'a' (the lowest band) to 'z' (the highest band). A technician may, in one operation, reassign the band recorded at any single slot on either tower's log to any lowercase letter. The two towers may be certified for simultaneous broadcast as soon as their logs satisfy at least one of the following:
Determine the minimum total number of reassignment operations required to satisfy at least one of the three certifications.
Line 1: two integers na and nb — the number of time slots logged by Tower A and by Tower B respectively.
Line 2: a string a of length na, lowercase letters — Tower A's log.
Line 3: a string b of length nb, lowercase letters — Tower B's log.
A single integer: the minimum number of reassignment operations needed.
1 <= na, nb <= 100000. a and b consist only of lowercase English letters, with lengths exactly na and nb.
Example 1
Input
3 3 aba caa
Expected
2
Explanation
Tower A's log is "aba" (frequencies a:2, b:1) and Tower B's log is "caa" (frequencies c:1, a:2). Condition (c) needs only 1 change per tower: change the single 'b' in Tower A to 'a' (log becomes "aaa"), and change the single 'c' in Tower B to 'a' (log becomes "aaa"). That is 2 operations total, and no split-point strategy for conditions (a) or (b) does better, so the answer is 2.
Example 2
Input
4 4 aaaa aaaa
Expected
0
Explanation
Both logs already use only the single letter 'a'. Condition (c) only requires each log individually to be one repeated letter — the two towers do not need to match each other — and this is already true with zero changes, so the answer is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →