CF 474A - Keyboard

CF 474A - Keyboard

Rating: 900
Tags: implementation
Solve time: 1m 4s
Verified: yes

Solution

Problem Understanding

The problem presents a keyboard with three rows of characters arranged exactly like a standard QWERTY layout. Mole is typing messages on this keyboard, but he accidentally shifted his hands either one key to the left or one key to the right. Because of this, the sequence of characters he typed does not match what he intended to write. Our task is to reverse this hand shift and reconstruct the original message.

The first input line tells us the direction of the shift: 'L' means Mole's hands moved left, so every typed character corresponds to the key immediately to its right on the keyboard, and 'R' means a right shift, so every typed character corresponds to the key immediately to its left. The second line is the sequence of characters Mole typed, which is guaranteed to be valid keys on this keyboard. The output should be the corrected string that represents what Mole intended to type.

The constraints are mild. The sequence has at most 100 characters, so any algorithm that examines each character individually will be fast enough. Edge cases include sequences consisting entirely of characters at the extreme ends of a row. For example, if the first row is qwertyuiop and the typed character is q with a left shift, there is no key to the left of q, but the problem guarantees this cannot happen. A careless solution might hard-code character replacements or forget to handle all three rows, which would fail on characters like ; or , in the lower rows.

Approaches

A brute-force approach would involve searching for each typed character in the keyboard rows and then moving one index left or right depending on the shift direction. This works because the keyboard is small, but it is cumbersome to write and repetitive. In a naive implementation, one might iterate over each row, check for the character, and then compute the index offset. This is correct, but it is verbose, error-prone, and unnecessarily repetitive. Its worst-case operation count is roughly 3 lookups per character times 100 characters, which is trivial, but the method is inelegant.

The optimal approach exploits the fixed keyboard layout. We can build a single mapping for all keys: for each character, store what key it maps to if shifted left and if shifted right. Then reconstructing the original string becomes a simple lookup for each typed character. The insight is that since the keyboard is static, precomputing the mapping reduces the problem to O(n) time, where n is the length of the typed string. The mapping guarantees we do not misalign rows and can handle all edge characters correctly under the problem's guarantees.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n * 3)	O(1)	Accepted, but verbose
Optimal	O(n)	O(1)	Accepted

Algorithm Walkthrough

1. Define the keyboard rows as strings: row1 = "qwertyuiop", row2 = "asdfghjkl;", row3 = "zxcvbnm,./". This represents the fixed layout of keys.
2. Concatenate the rows into a single string or maintain them separately to map each key to its neighbors. Each key's left neighbor is the character immediately before it in the row, and the right neighbor is the character immediately after it.
3. Read the direction of shift. If the direction is 'R', Mole’s hands moved right, which means the typed character is to the right of the intended key. To reconstruct the original message, we need the character to its left. Conversely, if the direction is 'L', we need the character to the right.
4. Iterate over each character in the typed string. For each character, find the row it belongs to. Then, depending on the shift direction, move one index left or right within that row to get the original character.
5. Append each corrected character to a result list and finally join it into a string to produce the output.

Why it works: Each character is guaranteed to be inside a row, and the shift is exactly one key, so looking up the neighboring key in the appropriate direction reconstructs the original message. The invariant is that at every iteration, we correctly map the typed key to the intended key according to the shift, which produces the correct message in sequence.

Python Solution

import sys
input = sys.stdin.readline

keyboard = ["qwertyuiop", "asdfghjkl;", "zxcvbnm,./"]

direction = input().strip()
typed = input().strip()

result = []

for c in typed:
    for row in keyboard:
        if c in row:
            idx = row.index(c)
            if direction == 'R':
                result.append(row[idx - 1])
            else:  # direction == 'L'
                result.append(row[idx + 1])
            break

print("".join(result))

In this code, we first define the keyboard layout as a list of rows. We then read the direction and the typed string. For each character, we search which row it belongs to and compute the correct original character by adjusting the index by -1 or +1 depending on the shift direction. Using a break ensures we stop searching once the row is found, preventing incorrect matches in other rows.

Worked Examples

Sample 1:

Input:

R
s;;upimrrfod;pbr

Trace:

Character	Row	Index	Shifted Index	Result
s	asdfghjkl;	1	0	a
;	asdfghjkl;	8	7	l
;	asdfghjkl;	8	7	l
u	qwertyuiop	4	3	y
p	qwertyuiop	9	8	o
i	qwertyuiop	7	6	u
m	zxcvbnm,./	6	5	n
r	qwertyuiop	3	2	e
r	qwertyuiop	3	2	e
f	asdfghjkl;	3	2	d
o	qwertyuiop	8	7	i
d	asdfghjkl;	2	1	s
;	asdfghjkl;	8	7	l
p	qwertyuiop	9	8	o
b	zxcvbnm,./	4	3	v
r	qwertyuiop	3	2	e

Output:

allyouneedislove

This confirms that each character is correctly mapped according to the shift direction.

Another example:

Input:

L
qwerty

Trace:

Character	Row	Index	Shifted Index	Result
q	qwertyuiop	0	1	w
w	qwertyuiop	1	2	e
e	qwertyuiop	2	3	r
r	qwertyuiop	3	4	t
t	qwertyuiop	4	5	y
y	qwertyuiop	5	6	u

Output:

wertyu

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is checked against at most three rows, which is negligible since n ≤ 100.
Space	O(n)	We store the corrected message in a list of length n.

Given the small input size, this linear solution executes efficiently and uses minimal memory, well within the 2-second time limit and 256 MB memory limit.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    keyboard = ["qwertyuiop", "asdfghjkl;", "zxcvbnm,./"]
    direction = input().strip()
    typed = input().strip()
    result = []
    for c in typed:
        for row in keyboard:
            if c in row:
                idx = row.index(c)
                if direction == 'R':
                    result.append(row[idx - 1])
                else:
                    result.append(row[idx + 1])
                break
    return "".join(result)

# provided sample
assert run("R\ns;;upimrrfod;pbr\n") == "allyouneedislove"

# custom cases
assert run("L\nqwerty\n") == "wertyu"  # simple left shift
assert run("R\nasdfg\n") == "qasdf"    # right shift, first row edge
assert run("L\nzxcvbnm\n") == "xcvbnm,"  # left shift, last row
assert run("R\np;/\n") == "o,l"  # extreme keys in last columns

Test input	Expected output	What it validates
R\ns;;upimrrfod;pbr	allyouneedislove	Standard case, mix of rows
L\nqwerty	wertyu	Left shift