Decode the Message

Easy
1016.

Decode the Message

Decode the Message is an easy coding problem on strings and hash table, asked in Amazon, Google and Zoho interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} key
 * @param {string} message
 * @return {string}
 */
var decodeMessage = function(key, message) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Decode the Message — Solution in Python, Java & C++

Decode the Message solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Decode the Message is an easy coding problem on strings and hash table, asked in Amazon, Google and Zoho interviews.

  • 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.

Hints for Decode the Message

  1. Hint 1

    Only the first occurrence of a letter in key matters; later ones are ignored.

  2. Hint 2

    A 26-slot table or a hash map is enough to hold the substitution.

  3. Hint 3

    Spaces pass through untouched, in both the key and the message.

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)

Java

public static String decodeMessage(String key, String message) {
    char[] table = new char[26];
    int next = 0;
    for (int i = 0; i < key.length(); i++) {
        char c = key.charAt(i);
        if (c != ' ' && table[c - 'a'] == 0) {
            table[c - 'a'] = (char) ('a' + next);
            next++;
        }
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < message.length(); i++) {
        char m = message.charAt(i);
        sb.append(m == ' ' ? ' ' : table[m - 'a']);
    }
    return sb.toString();
}

C++

string decodeMessage(string key, string message) {
    vector<char> table(26, 0);
    int next = 0;
    for (char c : key) {
        if (c != ' ' && table[c - 'a'] == 0) {
            table[c - 'a'] = (char) ('a' + next);
            next++;
        }
    }
    string out;
    for (char m : message) out += (m == ' ' ? ' ' : table[m - 'a']);
    return out;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets