We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Decode the Message

Number: 2406

Difficulty: Easy

Paid? No

Companies: Amazon, Tesla, Bloomberg, Coinbase

Problem Description

Given a cipher key and a secret message, the task is to decode the message using a substitution cipher. The substitution table is generated by taking the first appearance of every lowercase English letter in the key (ignoring spaces) and mapping them in order to the regular alphabet (a to z). Each character in the message is then replaced accordingly, and spaces are preserved.

Key Insights

  • The key string might contain duplicate letters and spaces; only the first occurrence of each letter matters.
  • Build a mapping (substitution table) from the key letters to the alphabet letters.
  • Loop through the message and replace each letter using the created mapping.
  • Maintain spaces in the message unchanged.

Space and Time 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 mapping holds at most 26 key-value pairs; additional space for the output message is O(m).

Solution

We first create a substitution table by iterating over the key string and collecting the first occurrence of each letter, ignoring spaces. These collected letters will be mapped to the alphabet from 'a' to 'z'. Then, for each character in the message, if it is a space, we leave it as is; otherwise, we substitute it using the table. This approach uses a hash map (or dictionary) for fast letter lookups, ensuring efficient substitution.

Code Solutions

# Function to decode the message
def decodeMessage(key: str, message: str) -> str:
    # Create a mapping from key characters to alphabet letters
    mapping = {}
    current_char = ord('a')  # Start mapping with 'a'
    
    # Iterate over each character in the key
    for letter in key:
        # Check if the character is an alphabet and is not yet mapped
        if letter != ' ' and letter not in mapping:
            mapping[letter] = chr(current_char)
            current_char += 1  # Move to the next letter in the alphabet
            # Stop early if we've mapped all 26 letters
            if current_char > ord('z'):
                break
    
    # Build the decoded message using the mapping
    decoded_message = []
    for char in message:
        # If the character is a space, preserve it
        if char == ' ':
            decoded_message.append(' ')
        else:
            decoded_message.append(mapping[char])
    
    return "".join(decoded_message)

# Example usage:
# key = "the quick brown fox jumps over the lazy dog"
# message = "vkbs bs t suepuv"
# print(decodeMessage(key, message))     # Output: "this is a secret"
← Back to All Questions