Author: Timur Degteari
Prepared by: Timur Degteari
In this problem, we can exploit the small constraints on both the name length (at most ) and the message length (at most ). This allows us to comfortably employ an O(n \cdot m) or even O(n \cdot m^2) solution.
We iterate over all possible starting positions where the encoded name might appear in the message. Specifically, we try each position from to n - m + 1 as a potential starting index.
For each candidate position , we examine the substring a[i], a[i+1], \ldots, a[i+m-1] and attempt to match each number with the corresponding letter from the name. During this process, we verify that:
Each letter in the name maps to exactly one number.
No two distinct letters map to the same number (i.e., the mapping is injective).
If this property holds, we have found a valid cypher. We then arbitrarily assign the remaining unused numbers to the letters that do not appear in the name (since these assignments will not affect the already-matched substring) and output the result.
If the property fails for all positions, we report that no valid cypher exists.
Time complexity: O(n \cdot m), where is the length of the encrypted message and is the length of the name.