Decide transform via one-to-one mapping
MathWorksSoftware Engineer · Online AssessmentLast updated
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. 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.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.