Loading page…
Practice problem · easy
A gift shop app lets customers preview a mirror keyring. The engraver prints a tag code on the ring, and a mirror tag shows the letters of the code in reverse order.
The tag has fixed slots. Every digit, dash and slash must stay in its own slot. Only the letters swap places.
You build the preview: given the code, return the mirror tag.
Write mirror_letters(code).
code holds letters a-z and A-Z, digits 0-9, and the symbols - and /.A stays A, wherever it moves.Input: code = "a1-bC/d2"
Output: "d1-Cb/a2"Pointers lo and hi start at the two ends. A pointer on a digit or symbol steps over it. When both pointers are on letters, the two letters swap and both pointers move in.
| lo | hi | At lo | At hi | Action | Code now |
|---|---|---|---|---|---|
| 0 | 7 | a | 2 | hi is on a digit: hi becomes 6 | a1-bC/d2 |
| 0 | 6 | a | d | both are letters: swap, lo becomes 1, hi becomes 5 | d1-bC/a2 |
| 1 | 5 | 1 | / | lo is on a digit: lo becomes 2 | d1-bC/a2 |
| 2 | 5 | - | / | lo is on a symbol: lo becomes 3 | d1-bC/a2 |
| 3 | 5 | b | / | hi is on a symbol: hi becomes 4 | d1-bC/a2 |
| 3 | 4 | b | C | both are letters: swap, lo becomes 4, hi becomes 3 | d1-Cb/a2 |
The pointers have crossed, so the walk ends.
Input: code = "7-8/9"
Output: "7-8/9"There are no letters, so nothing moves.
Input: code = "Ab-9"
Output: "bA-9"The letters A and b swap and keep their case. The dash and the digit stay put.
1 ≤ code.length ≤ 100,000 (characters on one tag)code contains only a-z, A-Z, 0-9, - and /Finding the matching letter from the back for every letter, starting the scan again each time, costs about n × n ÷ 2 steps. At n = 100,000 that is about 5 × 10^9, roughly 50 seconds at 10^8 operations a second. A walk with two pointers touches each character once, so at most 100,000 steps.
Strings cannot be edited in place in Python, Java and JavaScript. Building the answer by adding one character at a time copies the string again and again, which is also about n × n ÷ 2 steps. Work in an array of characters instead.
mirror_letters · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.