Letter Cipher Consistency
EasyArrays & Hashing
Problem
A puzzle magazine publishes substitution ciphers: every letter of the plain text is replaced by a code letter, the same plain letter always becomes the same code letter, and two different plain letters never share a code letter.
Given two strings plain and coded of equal length, return true if some such substitution turns plain into coded, and false otherwise. A letter may map to itself.
Example 1
- Input:
- plain = "noon", coded = "abba"
- Output:
- true
n → a and o → b, used consistently.
Example 2
- Input:
- plain = "abca", coded = "zyxw"
- Output:
- false
'a' would have to become both 'z' and 'w'.
Example 3
- Input:
- plain = "ab", coded = "aa"
- Output:
- false
'a' and 'b' would share the code letter 'a'.
Constraints
- 0 ≤ plain.length = coded.length ≤ 5·10^4
- Both strings contain printable ASCII characters.
Hint
Show the first hint
There are two ways to break the rules: one plain letter with two codes, or two plain letters with one code.
Walkthrough
How to approach it
01Clarify before coding
- Can a letter map to itself? Yes, that is allowed.
- Are the strings always the same length? Yes, guaranteed.
- Is the alphabet limited to letters? Any printable ASCII, so use hash maps (or 128-slot arrays).
02Brute force
For every pair of positions (i, j), check that plain[i] == plain[j] exactly when coded[i] == coded[j].
Cost: O(n²) time: 2.5·10^9 comparisons for n = 5·10^4.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.