ORIGINAL CODING QUESTION

Glyph edit distance

Return the fewest single-glyph insertions, deletions and substitutions converting the first sequence to the second. Every operation costs one.

Open practice workspace

Original exercise · medium. Editorial role relevance does not imply a company has asked this question.

Input and output

n, n glyph integers, m, m glyph integers. Print the requested integer.

Constraints

1 ≤ n,m ≤ 30; each glyph integer is in [0,25].

Example 1

Input

3 0 1 2 3 0 2 2

Output

Substitute the middle glyph for distance 1.

Example 2

Input

2 0 1 1 0

Output

Delete the last glyph for distance 1.

Explain your approach

Explain your time and auxiliary space complexity. Which input makes your algorithm work hardest?

Private grading inputs, expected outputs and canonical reference implementations are withheld. Authored expected outputs were cross-checked with independent reference oracles; compiler/runtime behavior still needs a verified execution provider.

Hint 1

Compare the last glyphs of two prefixes.

Hint 2

Matching glyphs need no operation.

Hint 3

Otherwise minimize insertion, deletion and replacement.

Practice this question

Save your work privately, explain decisions and return to your revision queue.

Open practice workspace Browse the question library →