LeetCode 2325 - Decode the Message

Difficulty: 🟢 Easy
Topics: Hash Table, String

Solution

Problem Understanding

This problem is asking us to decode a secret message using a substitution cipher defined by a key string. The key string may include spaces and contains every lowercase letter of the English alphabet at least once. The order in which each letter first appears in the key determines the mapping to the regular alphabet. For example, the first unique letter in the key maps to 'a', the second unique letter to 'b', and so on. Spaces in the message remain unchanged. The input key can have up to 2000 characters and message can also have up to 2000 characters, so efficiency matters but we are not dealing with extremely large inputs. Edge cases to consider include keys with repeated letters and messages consisting entirely of spaces.

The expected output is a fully decoded string where each letter has been substituted according to the mapping defined by the key. The constraints guarantee that the key always includes all 26 letters and that both strings consist of lowercase letters and spaces, which simplifies the problem as we do not need to handle unexpected characters.

Approaches

A brute-force approach would involve iterating over the key string multiple times to determine the mapping for each letter, then substituting each letter in the message using this mapping. While this works, it is inefficient because repeatedly scanning for the first appearance of each letter can lead to unnecessary repeated work, especially if the key is long.

The optimal approach leverages a hash map to record the first appearance of each letter in a single pass. We maintain a mapping from the letters in the key to 'a' through 'z'. Once the mapping is established, decoding the message is straightforward: for each character in the message, we replace it using the hash map if it is a letter, or leave it unchanged if it is a space. This reduces the operation to a single scan of the key and one scan of the message, resulting in linear time complexity relative to the length of the input strings.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(26 * key.length + message.length)	O(26)	Repeatedly scan key to find first occurrences, then decode message
Optimal	O(key.length + message.length)	O(26)	Single pass to build mapping, single pass to decode message

Algorithm Walkthrough

Initialize an empty dictionary (hash map) to store the mapping from key letters to the regular alphabet. Also, maintain a variable to track the current letter in the alphabet starting from 'a'.
Iterate through each character in the key string. If the character is a space, skip it. If the character has not been seen before in the mapping, map it to the current alphabet letter and advance the alphabet letter by one.
After scanning the key, the dictionary now contains a complete substitution table for all 26 letters.
Initialize an empty list to build the decoded message. Iterate over each character in the message string. If the character is a space, append a space to the list. Otherwise, look up the character in the dictionary and append the corresponding decoded letter.
Join all characters in the list to form the final decoded string and return it.

Why it works: By recording the first appearance of each letter and mapping it to the alphabet sequentially, we preserve the substitution rules exactly as described. Spaces are left unchanged, and every message character is guaranteed to have a mapping because the key includes all letters.

Python Solution

class Solution:
    def decodeMessage(self, key: str, message: str) -> str:
        mapping = {}
        current_char = 'a'
        
        for char in key:
            if char == ' ':
                continue
            if char not in mapping:
                mapping[char] = current_char
                current_char = chr(ord(current_char) + 1)
                if current_char > 'z':
                    break
        
        decoded_chars = []
        for char in message:
            if char == ' ':
                decoded_chars.append(' ')
            else:
                decoded_chars.append(mapping[char])
        
        return ''.join(decoded_chars)

The Python implementation follows the algorithm exactly. It uses a dictionary to record first occurrences of letters, ensures spaces are skipped when building the mapping, and constructs the decoded message efficiently using a list before joining into a string. The break condition after 'z' is optional but slightly improves efficiency if the key is longer than needed.

Go Solution

func decodeMessage(key string, message string) string {
    mapping := make(map[rune]rune)
    currentChar := 'a'
    
    for _, char := range key {
        if char == ' ' {
            continue
        }
        if _, exists := mapping[char]; !exists {
            mapping[char] = currentChar
            currentChar++
            if currentChar > 'z' {
                break
            }
        }
    }
    
    decoded := make([]rune, len(message))
    for i, char := range message {
        if char == ' ' {
            decoded[i] = ' '
        } else {
            decoded[i] = mapping[char]
        }
    }
    
    return string(decoded)
}

The Go implementation mirrors Python logic but handles runes explicitly since Go strings are UTF-8 encoded. A map is used for the substitution table, and a rune slice is used to efficiently build the decoded message before converting it to a string.

Worked Examples

Example 1:

key = "the quick brown fox jumps over the lazy dog"

message = "vkbs bs t suepuv"

Step 1: Build mapping. Iterate over key:

Key Letter	Mapping Letter
t	a
h	b
e	c
q	d
u	e
i	f
c	g
k	h
b	i
r	j
o	k
w	l
n	m
f	n
x	o
j	p
m	q
p	r
s	s
v	t
l	u
a	v
z	w
y	x
d	y
g	z

Step 2: Decode message:

Message Char	Decoded Char
v	t
k	h
b	i
s	s
(space)	(space)
b	i
s	s
(space)	(space)
t	a
(space)	(space)
s	s
u	e
e	c
p	r
u	e
v	t

Final decoded message: "this is a secret"

Example 2 follows the same logic with a pre-defined mapping.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(key.length + message.length)	Single pass over key to build mapping, single pass over message to decode
Space	O(26 + message.length)	Hash map stores 26 letters, list/slice stores decoded message

The complexity is linear relative to the input sizes, which is efficient given the constraints.

Test Cases

# Provided examples
assert Solution().decodeMessage("the quick brown fox jumps over the lazy dog", "vkbs bs t suepuv") == "this is a secret"
assert Solution().decodeMessage("eljuxhpwnyrdgtqkviszcfmabo", "zwx hnfx lqantp mnoeius ycgk vcnjrdb") == "the five boxing wizards jump quickly"

# Edge cases
assert Solution().decodeMessage("abcdefghijklmnopqrstuvwxyz", "a b c") == "a b c"  # direct mapping
assert Solution().decodeMessage("abcdefghijklmnopqrstuvwxyz", "z y x") == "z y x"  # reverse letters in message
assert Solution().decodeMessage("the quick brown fox jumps over the lazy dog", "     ") == "     "  # spaces only

Test	Why
first example	verifies correct decoding with spaces
second example	verifies decoding with a pre-defined complex key
direct mapping	ensures no transformations occur if key is sequential
reverse letters	ensures letters are mapped correctly even if message letters appear later
spaces only	ensures spaces are preserved correctly

Edge Cases

One edge case is when the key contains many repeated letters before covering all letters. The implementation correctly skips duplicates and only maps the first occurrence, ensuring that the correct sequential alphabet is used.

Another edge case is when the message consists entirely of spaces. Since spaces are explicitly handled, the output correctly preserves them without mapping.

A third edge case is when the message includes letters at the end of the alphabet, such as 'z', and the key maps them last. The implementation guarantees that all letters are mapped before decoding, so the message is decoded correctly regardless of letter position in the key.