Decide transform via one-to-one mapping
Company: MathWorks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given two strings s and t of equal length over the lowercase English alphabet. In one step, you may pick any character x and replace all its occurrences in s with a single character y (the mapping x→y must be applied consistently across the entire string and persists for subsequent steps). Determine whether s can be transformed into t in finitely many steps. If cycles occur in the mapping, you may only break them if there exists at least one spare character not present in t to use as a temporary buffer. Design an algorithm to decide transformability and, if possible, output one valid sequence of replacements.
Quick Answer: This question evaluates understanding of character-to-character mappings in strings, modeling those mappings as directed graphs, detection and handling of cycles, and the ability to construct a sequence of replacements.
You are given two strings `s` and `t` of equal length over the lowercase English alphabet (`'a'`-`'z'`). In one step you may pick any character `x` and replace ALL of its current occurrences in `s` with a single character `y`. The mapping `x -> y` is applied consistently across the entire string and persists for subsequent steps. Determine whether `s` can be transformed into `t` in finitely many such steps.
Return `true` if the transformation is possible, otherwise `false`.
Key observations:
- Every distinct character of `s` must map to exactly one character of `t` (if the same source character must become two different targets, it is impossible).
- If `s` already equals `t`, zero steps are needed, so it is trivially possible.
- If `s != t`, replacements may create cyclic dependencies (e.g. `a -> b` and `b -> a`). A cycle can only be broken if there is at least one spare character (one of the 26 letters that does NOT appear in `t`) to use as a temporary buffer. Hence when `s != t`, the transformation is possible if and only if `t` uses fewer than 26 distinct characters.
Constraints
- 1 <= len(s) == len(t) <= 10^5 (the strings have equal length)
- s and t consist only of lowercase English letters 'a'-'z'
- Empty strings are considered equal and trivially transformable
Examples
Input: ("aabcc", "ccdee")
Expected Output: True
Explanation: Map a->c, b->d, c->e applied carefully (process in an order that avoids overwriting). t uses 3 distinct chars (< 26), so a spare buffer exists. Transformable.
Input: ("leetcode", "codeleet")
Expected Output: False
Explanation: Character 'e' in s would need to map to multiple different characters in t, violating the consistent one-to-one mapping requirement. Not transformable.
Hints
- First check that the mapping from s to t is a function: each distinct character in s must always correspond to the same character in t. If any source character needs two different targets, it is impossible.
- If s already equals t, the answer is immediately true (no steps required).
- When s != t, replacements can form cycles. You need a 'free' letter (one not used anywhere in t) to serve as a temporary holding spot. So the answer is true iff t has fewer than 26 distinct characters.