How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at MathWorks.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at MathWorks during technical interviews.

Decide transform via one-to-one mapping | MathWorks Coding Question

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.

Input: ("", "")

Expected Output: True

Explanation: Two empty strings are equal, so zero steps are needed.

Input: ("a", "b")

Expected Output: True

Explanation: Single mapping a->b; t uses 1 distinct char, plenty of spare buffers. Transformable.

Input: ("ab", "ba")

Expected Output: True

Explanation: Requires the cycle a<->b. Since t = 'ba' uses only 2 of 26 letters, a spare character (e.g. 'c') can buffer the swap: a->c, b->a, c->b. Transformable.

Input: ("abcdefghijklmnopqrstuvwxyz", "bcdefghijklmnopqrstuvwxyza")

Expected Output: False

Explanation: A full 26-letter rotation forms one big cycle, but t uses all 26 letters so there is NO spare buffer character to break it. Not transformable.

Input: ("aa", "bc")

Expected Output: False

Explanation: The same source character 'a' would have to become both 'b' and 'c', which is impossible under a consistent mapping.

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.

Quick Overview

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.