Decode the Message — Editorial

Opening the reading…

Intuitionthe key defines a new alphabet by first appearance

The key is not itself a sentence to decode; it is an ordering of the original letters. Ignore spaces and scan from left to right. The first unseen letter becomes a, the next unseen letter becomes b, and so on until all 26 letters have a replacement. Repeated letters do not create new entries because their first appearance already fixed their meaning.

Once that table exists, decoding is independent for each character in the message. A letter is replaced by its mapped letter, while a space is copied directly. The two scans have different jobs: the key creates the rules, and the message uses them. Keeping those jobs separate prevents a repeated key letter or a message space from changing the table.

Approach

Create an empty mapping and set the next decoded letter to a, because every source letter must receive the next unused alphabet letter in order.

Scan key from left to right, because the first occurrence determines the mapping and later occurrences must not overwrite it.

Skip spaces in key, because spaces are separators rather than letters and must not consume a decoded alphabet position.

When a letter is not already mapped, assign it the current decoded letter and advance that letter, because only first appearances introduce new substitutions.

Create an empty answer and scan message from left to right, because the output must preserve the message's original order.

Copy message spaces directly and look up every other character in the mapping, because spaces are unchanged while every lowercase letter has a table entry.

Return the completed answer after the scan, because each output character has already been decoded exactly once.

Complexitytwo linear scans and a fixed-size table

MEASURE	BOUND	WHY
Time	O(n + m)	The key is scanned once to create the table and the message is scanned once to produce the answer. Each map operation concerns one of at most 26 distinct lowercase letters, so the work per character stays constant and no character is revisited.
Space	O(1) extra	The mapping contains at most 26 entries and the next-letter variable uses constant space. The returned string is required output and is excluded from the extra-space bound, so the bound does not grow with the shape of key or message.

n is the length of key and m is the length of message.

Annotated solutionC++ · two scans · direct substitution table

CPPBuild the first-occurrence mapping, then translate every message character.

#include <string>
#include <unordered_map>
using namespace std;

class Solution {
public:
    string decodeMessage(string key, string message) {
        unordered_map<char, char> mapping;
        char nextLetter = 'a';

        for (char c : key) {
            if (c != ' ' && mapping.find(c) == mapping.end()) {
                mapping[c] = nextLetter;
                ++nextLetter;
            }
        }

        string answer;
        for (char c : message) {
            if (c == ' ') {
                answer += ' ';
            } else {
                answer += mapping[c];
            }
        }

        return answer;
    }
};

The condition mapping.find(c) == mapping.end() is the key to the construction. Without it, a repeated letter in key would receive a later alphabet character and overwrite the meaning established by its first appearance. The separate space branch in the second loop keeps spaces from being treated as lookup keys and preserves the message's word boundaries.