Get started

Decode the Message — Easy Problem & Solution

Build a substitution table from key: walk it left to right and the first time each new letter appears, map it to 'a', then 'b', then 'c', and so on.

  • Difficulty: Easy
  • Topics: Strings, Hash Table
  • Asked at: Amazon, Google, Zoho
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Build a substitution table from key: walk it left to right and the first time each new letter appears, map it to 'a', then 'b', then 'c', and so on. Spaces in key are skipped.

Decode message with that table, leaving its spaces in place, and return the result.

Example 1

Input: key = "codekairo builds the fastest judge in every language zxq w mvp", message = "rbnk yrk dfekn"
Output: hire the coder
Explanation: `c`→`a`, `o`→`b`, `d`→`c`, … so `r`→`h`, `b`→`i`, `n`→`r`, `k`→`e`.

Example 2

Input: key = "the quick brown fox jumps over the lazy dog", message = "vkbs bs t suepuv"
Output: this is a secret

Example 3

Input: key = "eljuxhpwnyrdgtqkviszcfmabo", message = "zwx hnfx lqantp mnoeius ycgk vcnjrdb"
Output: the five boxing wizards jump quickly

Constraints

  • 26 <= key.length <= 2000
  • key consists of lowercase English letters and spaces.
  • key contains every letter in the English alphabet at least once.
  • 1 <= message.length <= 2000
  • message consists of lowercase English letters and spaces.

How to solve Decode the Message

One pass over key builds the table — each unseen letter claims the next letter of the alphabet — and a second pass rewrites message through it.

Approach

  1. Walk key; on a letter not yet in the table, map it to 'a' + next and advance next.
  2. Walk message; emit a space unchanged, otherwise the mapped letter.

Why it works

The "first occurrence only" rule is what makes the table a well-defined bijection — the key is longer than 26 characters and letters repeat, so overwriting on every occurrence would scramble the mapping. The alphabet guarantee means every letter in message is certain to have an entry.

Complexity

  • Time — O(len(key) + len(message))
  • Space — O(1) — at most 26 entries

Pitfalls

  • Overwriting the map on repeat occurrences breaks the decoding.
  • Spaces must be skipped when assigning letters, or they would consume a slot.
  • The table maps key-letter → plain-letter; inverting it decodes backwards.

Reference solution

Python

def decodeMessage(key: str, message: str) -> str:
    table = {}
    nxt = 0
    for c in key:
        if c != " " and c not in table:
            table[c] = chr(ord("a") + nxt)
            nxt += 1
    return "".join(" " if c == " " else table[c] for c in message)

JavaScript

var decodeMessage = function(key, message) {
    var table = {}, next = 0, i;
    for (i = 0; i < key.length; i++) {
        var c = key.charAt(i);
        if (c !== " " && table[c] === undefined) {
            table[c] = String.fromCharCode(97 + next);
            next++;
        }
    }
    var out = "";
    for (i = 0; i < message.length; i++) {
        var m = message.charAt(i);
        out += m === " " ? " " : table[m];
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue