Check whether each word is a candidate, then count only candidate words. Consider one test case, and let be the maximum length among and all ciphertext words.
Since the ciphertext words appear before in the input, store the words first and then read . A word with a different length from cannot be a candidate. Otherwise, initialize two arrays of size . The first records the ciphertext letter assigned to each plaintext letter, and the second records the plaintext letter assigned to each ciphertext letter.
Process the letters at each corresponding position. Reject if was already assigned to a different letter or if was already assigned from a different letter. Otherwise, record the correspondence in both arrays. If no contradiction occurs, is a candidate. Reset both arrays before checking the next word, since the substitutions are independent.
Use an ordered map whose keys are the actual candidate strings to count their occurrences. If there are no candidates, output -1. Otherwise, choose a key with the largest frequency, breaking ties by choosing the lexicographically smallest key. Different strings must be counted separately even if they have the same substitution pattern.
Checking candidates takes time. A string comparison takes time, so the total time complexity with an ordered map is . The space complexity is .
Proof
Suppose a valid substitution turns into . Their lengths must be equal. Equal plaintext letters have equal ciphertext letters, so the first array cannot encounter a contradiction. Different plaintext letters have different ciphertext letters, so the second array cannot encounter a contradiction either. Therefore, every candidate passes the check.
Conversely, suppose passes the check. Every letter occurring in is assigned to exactly one ciphertext letter, and different plaintext letters are assigned to different ciphertext letters. Thus, the recorded assignments are a one-to-one correspondence between the letters used in the two words. The numbers of unassigned plaintext letters and unused ciphertext letters are equal. Pair them arbitrarily to extend the recorded assignments to a valid substitution on all letters. This substitution turns into exactly , so every word passing the check is a candidate.
In subtask 1, every word has length , so every ciphertext word is a candidate. Count the occurrences of each letter in an array of size and select the answer in time and space.
In subtask 2, candidate checking can compare every pair of positions in equal-length words and verify that and have the same truth value. For each candidate, directly compare it with every input word to count its occurrences. This takes time and space to store the words.
Each input word is processed once, and its string's count is incremented exactly when it is a candidate. The map therefore stores the exact frequency of each candidate. Selecting the highest frequency and then the lexicographically smallest tied word gives precisely the required answer.
Solution written by GPT6
