Skip to main content
Talentd

Decode the Message - Solution & Explanation

EasyHash TableString13 min readAsked at: Amazon, Meta, Coinbase +1
Practice this problem

Problem Statement

You are given the strings key and message, which represent a cipher key and a secret message, respectively. The steps to decode message are as follows:

  1. Use the first appearance of all 26 lowercase English letters in key as the order of the substitution table.
  2. Align the substitution table with the regular English alphabet.
  3. Each letter in message is then substituted using the table.
  4. Spaces ' ' are transformed to themselves.
  • For example, given key = "happy boy" (actual key would have at least one instance of each letter in the alphabet), we have the partial substitution table of ('h' -> 'a', 'a' -> 'b', 'p' -> 'c', 'y' -> 'd', 'b' -> 'e', 'o' -> 'f').

Return the decoded message.

 

Example 1:

Input: key = "the quick brown fox jumps over the lazy dog", message = "vkbs bs t suepuv"
Output: "this is a secret"
Explanation: The diagram above shows the substitution table.
It is obtained by taking the first appearance of each letter in "the quick brown fox jumps over the lazy dog".

Example 2:

Input: key = "eljuxhpwnyrdgtqkviszcfmabo", message = "zwx hnfx lqantp mnoeius ycgk vcnjrdb"
Output: "the five boxing wizards jump quickly"
Explanation: The diagram above shows the substitution table.
It is obtained by taking the first appearance of each letter in "eljuxhpwnyrdgtqkviszcfmabo".

 

Constraints:

  • 26 <= key.length <= 2000
  • key consists of lowercase English letters and ' '.
  • key contains every letter in the English alphabet ('a' to 'z') at least once.
  • 1 <= message.length <= 2000
  • message consists of lowercase English letters and ' '.

Approach Overview

Problem Overview: You receive a key string representing a substitution cipher and a message string encoded with that cipher. The first appearance of each character in key maps sequentially to the alphabet (a to z). Spaces stay unchanged. The task is to reconstruct the mapping and decode the original message.

Approach 1: HashMap for Character Mapping (O(n) time, O(1) space)

This approach builds the substitution table explicitly using a hash table. Iterate through the key from left to right and assign each new character to the next unused letter in the alphabet. Skip spaces and ignore characters already mapped. Once the mapping is built, iterate through the message and replace each character using constant-time hash lookups. Spaces are copied directly. Since the alphabet size is fixed at 26, the hash table remains small and effectively constant space.

The key insight: the cipher order is determined by the first occurrence of characters in the key. A hash map makes it trivial to check whether a character has already been assigned and to retrieve its mapped value instantly. This approach is clean, readable, and works naturally with most programming languages.

Approach 2: Character Array Substitution (O(n) time, O(1) space)

This method replaces the hash table with a fixed-size array of length 26. Each index represents a letter (index = char - 'a') and stores its mapped value. While scanning the key, fill the array whenever you encounter a character that has not yet been assigned. Track the next available alphabet character and advance it as mappings are created.

Decoding works by iterating through the message and performing direct array lookups. This avoids hashing overhead and relies purely on arithmetic indexing. The logic is essentially the same as the hash map solution, but with a slightly lower constant factor.

Because the alphabet size is fixed, the substitution array consumes constant memory and guarantees O(1) access time. Problems involving character substitution or frequency counting often benefit from this pattern when working with string data and small character sets.

Recommended for interviews: The hash map solution is typically expected because it clearly demonstrates understanding of substitution mapping and efficient lookups. The array-based version is a small optimization that shows awareness of constant-factor improvements and fixed alphabet constraints. Both run in O(n) time where n is the length of the key plus the message.

Approach 1: Approach using HashMap for Mapping

This approach involves using a HashMap or a dictionary to map the first occurrence of each letter in the key to the English alphabet sequentially. Ignore spaces in the key, and once the substitution table is created, use it to decode the message by substituting each character accordingly. Ensure spaces in the message are retained as spaces.

The function creates a dictionary to map each first unique letter in the 'key' to the corresponding letter in the English alphabet. The 'decoded_message' lists each character’s substitution and combines them into a string.

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

Time Complexity: O(n + m), where n is the length of the key and m is the length of the message.
Space Complexity: O(1), as the space used for mapping is constant (26 letters only).

Try this approach in the editor →

Approach 2: Character Array Substitution

This method uses a fixed-size character array to implement a direct character mapping. Characters are indexed by their ASCII values, and substitutions are performed using direct array lookups. This approach avoids using hash maps similar to hash tables.

This solution uses a list of fixed size (26) for mapping, leveraging ASCII values to directly index and place mapped values. Decoding checks spaces separately.

Code

PythonCJavaScript

Python

C

JavaScript

Complexity

Time Complexity: O(n + m), where n is the length of the key and m is the length of the message.
Space Complexity: O(1), using a fixed size array for character mapping.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach using HashMap for Mapping

Time Complexity: O(n + m), where n is the length of the key and m is the length of the message.
Space Complexity: O(1), as the space used for mapping is constant (26 letters only).

Character Array Substitution

Time Complexity: O(n + m), where n is the length of the key and m is the length of the message.
Space Complexity: O(1), using a fixed size array for character mapping.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
HashMap for Character MappingO(n)O(1)General approach. Clear and easy to implement in interviews using a hash table.
Character Array SubstitutionO(n)O(1)When optimizing constant factors or working with fixed lowercase alphabets.

Video Solution

Weekly Contest 300 | Leetcode 2325 Decode the Message | Easy DP • Coding Decoded • 3,898 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Decode the Message easy or hard?
Decode the Message is classified as an Easy problem with a high acceptance rate. The main requirement is understanding how to build a substitution mapping from the first occurrence order of characters in the key. Once the mapping is built, decoding the message is straightforward.
How to solve Decode the Message in O(n)?
First scan the key and assign each unique character to the next letter in the alphabet while skipping spaces. Store this mapping in a hash map or a 26-length array. Then iterate through the message and replace each character using the mapping while preserving spaces. Both steps are linear, resulting in O(n) time.
What is the best approach for Decode the Message?
The best approach uses a hash map to build the substitution mapping from the key string. Each new character in the key is mapped sequentially to letters from 'a' to 'z'. After constructing the map, iterate through the message and replace characters using constant-time lookups. This solution runs in O(n) time and O(1) space because the alphabet size is fixed.
What data structure is used in Decode the Message?
The primary data structure is a hash table (or dictionary) that stores mappings between encoded characters and decoded alphabet characters. An alternative implementation uses a fixed-size character array indexed by letter position, which provides constant-time access without hashing.
What is the time complexity of Decode the Message?
The time complexity is O(n), where n is the combined length of the key and the message. One pass builds the substitution mapping from the key, and another pass decodes the message. Each lookup is constant time due to hash map or array indexing.
Decode the Message Python or Java solution approach?
Both Python and Java implementations typically build a mapping from the key using a dictionary or HashMap. After constructing the mapping, iterate through the message and append the mapped characters to the result string while keeping spaces unchanged. The algorithm runs in O(n) time and constant space.
Is Decode the Message asked at Google, Amazon, or Meta?
This problem represents a typical string and hash table pattern that appears in coding interviews at companies like Amazon and Google. While the exact question may vary, building substitution mappings and performing efficient character transformations is a common interview theme.

Ready to solve this problem?

Practice Decode the Message with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters