Decode the Message

Difficulty: Easy | Acceptance: 85.80% | Paid: No Topics: Hash Table, String

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

1. Use the first occurrence of each letter in key to replace the corresponding letter in the English alphabet (a, b, c, …, z) with that letter.
2. Replace every letter in message with the letter that it is mapped to in the substitution table.
3. Return the decoded message.

• Examples
• Constraints
• Hash Map
• Array Mapping

Examples

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 substitution table is built based on the key:
't' -> 'a', 'h' -> 'b', 'e' -> 'c', ' ' -> ' ', 'q' -> 'd', 'u' -> 'e', ...
The decoded message is "this is a secret".

Example 2:

Input: key = "eljuxspwnhldybcgmkfqoiuztewvry", 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 ' '.
key contains every letter in the English alphabet at least once.
1 <= message.length <= 2000
message consists of lowercase English letters and ' '.

Hash Map

Intuition We can iterate through the key string to build a mapping (dictionary) from each unique character to the corresponding letter in the standard alphabet (‘a’ to ‘z’). Then, we iterate through the message and substitute each character using this map.

Steps

• Initialize an empty hash map and a variable representing the current target character starting at ‘a’.
• Iterate through each character in the key.
• If the character is a space, skip it.
• If the character is not already in the map, add it with the current target character as its value, then increment the target character.
• Iterate through the message. If the character is a space, append it to the result. Otherwise, append the mapped value from the hash map.
• Return the constructed result string.

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)
        
        result = []
        for char in message:
            if char == ' ':
                result.append(' ')
            else:
                result.append(mapping[char])
                
        return ''.join(result)

Complexity

• Time: O(N + M), where N is the length of key and M is the length of message. We iterate through both strings once.
• Space: O(1), because the hash map will store at most 26 entries (one for each letter of the alphabet), which is constant space.
• Notes: Hash map provides O(1) average time complexity for lookups.

Array Mapping

Intuition Since the input consists only of lowercase English letters, we can use a fixed-size array of length 26 to store the substitution mapping. This avoids the overhead of a hash map and provides direct index access.

Steps

• Create a character array (or integer array) of size 26 to act as the substitution table.
• Initialize a boolean array or set to keep track of which letters from the key have been processed.
• Iterate through the key. For each valid character, calculate its index (0-25). If it hasn’t been processed, map it to the next character in the alphabet sequence (‘a’ + index) and mark it as processed.
• Iterate through the message. If the character is a space, append it. Otherwise, use the character’s index to look up the decoded character in the substitution array and append it.

class Solution:
    def decodeMessage(self, key: str, message: str) -> str:
        substitution = [''] * 26
        seen = set()
        curr = 0
        
        for char in key:
            if char == ' ':
                continue
            if char not in seen:
                seen.add(char)
                substitution[ord(char) - ord('a')] = chr(ord('a') + curr)
                curr += 1
                
        result = []
        for char in message:
            if char == ' ':
                result.append(' ')
            else:
                result.append(substitution[ord(char) - ord('a')])
                
        return ''.join(result)

Complexity

• Time: O(N + M), where N is the length of key and M is the length of message.
• Space: O(1), as we use fixed-size arrays of length 26.
• Notes: This approach is generally faster than the hash map approach due to lower overhead and direct memory access, though the difference is negligible for small input sizes.