Decide transform via one-to-one mapping
Problem Description
You are provided with two strings, s and t, which are of equal length and composed solely of lowercase English alphabet characters.
The allowed operation is as follows:
In a single step, you can select any character x currently present in string s and replace all its occurrences within s with a chosen character y. This x → y mapping must be applied consistently across the entire string s and will persist for all subsequent steps.
Your task is to:
- Determine whether string
scan be transformed into stringtusing a finite number of these steps. - If transformation is possible, design an algorithm that outputs one valid sequence of replacements (e.g.,
a->b,c->d, ...).
Special Constraint: Cycle Resolution
If a cycle occurs in the character mapping (e.g., a → b → c → a), such a cycle can only be broken if there is at least one "spare" character available. A "spare" character is defined as any lowercase English alphabet character that is not present in the target string t. This spare character can be used as a temporary buffer to facilitate the cycle break.
AI interview prep
Core dilemma
The central engineering conflict is managing the evolving, directed character mappings while robustly detecting and resolving cycles under the strict condition of having an available "spare" character not present in the target string `t`. This involves balancing the greedy application of mappings with the foresight needed to avoid or break cycles efficiently.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Decide transform via one-to-one mapping
Problem Description
You are provided with two strings, s and t, which are of equal length and composed solely of lowercase English alphabet characters.
The allowed operation is as follows:
In a single step, you can select any character x currently present in string s and replace all its occurrences within s with a chosen character y. This x → y mapping must be applied consistently across the entire string s and will persist for all subsequent steps.
Your task is to:
- Determine whether string
scan be transformed into stringtusing a finite number of these steps. - If transformation is possible, design an algorithm that outputs one valid sequence of replacements (e.g.,
a->b,c->d, ...).
Special Constraint: Cycle Resolution
If a cycle occurs in the character mapping (e.g., a → b → c → a), such a cycle can only be broken if there is at least one "spare" character available. A "spare" character is defined as any lowercase English alphabet character that is not present in the target string t. This spare character can be used as a temporary buffer to facilitate the cycle break.