Consistent Letter Relabel
EasyTries & Strings
Problem
A cipher replaces letters one for one: every occurrence of a letter becomes the same new letter, and two different letters never become the same letter. A letter may map to itself.
Given strings s and t of equal length, return true if some such cipher turns s into t.
Example 1
- Input:
- s = "noon", t = "peep"
- Output:
- true
n → p and o → e.
Example 2
- Input:
- s = "abca", t = "zyxw"
- Output:
- false
a would have to become both z and w.
Example 3
- Input:
- s = "ab", t = "aa"
- Output:
- false
a and b would both become a.
Constraints
- 1 ≤ s.length = t.length ≤ 5·10^4
- Strings consist of printable ASCII characters.
Hint
Show the first hint
A valid cipher is a function from letters of s to letters of t that is also one-to-one.
Walkthrough
How to approach it
01Clarify before coding
- Can a letter map to itself? Yes.
- Must the mapping be one-to-one? Yes: two different letters of s may not become the same letter.
- Are lengths always equal? Yes, by the constraints.
02Brute force
For every pair of positions (i, j), check that s[i] == s[j] exactly when t[i] == t[j].
Cost: O(n²) comparisons: 2.5·10^9 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.