Replace All Letters

Hard

A text editor has a "replace all" command for a single letter: you pick a lowercase English letter x and any other lowercase English letter y, and every occurrence of x in the string becomes y at once. You are given strings source and target of the same length. Can source be turned into target by using this command any number of times, possibly zero? Return True or False.

Example 1

source='xxyz', target='zzxy' → True

The letters must rotate: x → z, y → x, z → y. Whichever of these goes first would merge two groups of letters, so z is parked on a spare letter first: xxyz → xxyq → zzyq → zzxq → zzxy.

Example 2

source='aab', target='abb' → False

The two as can only change together, yet in target they correspond to different letters, a and b.

Example 3

source='abcdefghijklmnopqrstuvwxyz', target='bcdefghijklmnopqrstuvwxyza' → False

All 26 letters must rotate, but every letter of the alphabet is in use, so there is no spare one. The very first replacement merges two letters, and they can never be told apart again.

Constraints

1 ≤ source.length ≤ 10⁵
target.length == source.length
source and target consist of lowercase English letters only

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Hash Table String