Determine a one-step string transformation
Company: Jerry.Ai
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Given two lowercase strings `source` and `target`, determine whether `target` can be obtained from `source` using at most one of the following operations, and output one valid operation if possible.
Allowed operations:
1. `add c`: Insert one character `c` at any position in `source`.
2. `delete c`: Delete one occurrence of character `c` from `source`.
3. `replace x y`: Replace one occurrence of character `x` in `source` with character `y`.
4. `move c`: Remove one occurrence of character `c` from its current position and insert it at another position in the string.
If `source` is already equal to `target`, output `no_change`. If no single operation can transform `source` into `target`, output `impossible`. If multiple valid operations exist, output any one valid operation.
Examples:
```text
source = "baren", target = "bbren"
output: replace a b
```
```text
source = "banan", target = "banana"
output: add a
```
```text
source = "abcde", target = "acdeb"
output: move b
```
Expected follow-up: design an efficient solution that handles long strings, ideally in linear time.
Quick Answer: This question evaluates proficiency in string manipulation and algorithmic reasoning, focusing on edit operations, positional changes, and edge-case handling.
Return a deterministic operation describing how to transform source into target using at most one add, delete, replace, or move operation, or return impossible.
Constraints
- source and target are lowercase strings.
- Return no_change if the strings are already equal.
- When several operations could work, this grader prefers add/delete, then replace, then the first left-to-right move.
Examples
Input: ('baren', 'bbren')
Expected Output: 'replace a b'
Explanation: One replacement changes a to b.
Input: ('banan', 'banana')
Expected Output: 'add a'
Explanation: One insertion adds the final a.
Hints
- Length difference determines add and delete cases.
- For equal lengths, check replacement before testing moves.