Cypher#494

Cypher (Editorial)

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.