Problem Description

This problem asks you to decode a secret message using a substitution cipher created from a given key string.

The decoding process works as follows:

1. Build the substitution table: Go through the key string and record the first occurrence of each lowercase letter. The order in which these letters appear becomes your substitution mapping.

2. Create the mapping: Map each unique letter from the key to the regular alphabet in order. The first unique letter maps to 'a', the second to 'b', the third to 'c', and so on.

3. Decode the message: Replace each letter in the message string using your substitution table. Spaces remain unchanged.

Example: Given key = "happy boy":

• Extract unique letters in order: h, a, p, y, b, o (ignoring the duplicate 'p' and 'y')
• Create mapping:
  • h → a
  • a → b
  • p → c
  • y → d
  • b → e
  • o → f
  • (remaining letters would follow...)

If message = "hap", it would decode to "abc" using the mapping above.

The solution builds a dictionary d to store the character mappings. It iterates through the key string, adding each new character to the dictionary with its corresponding alphabet letter (using ascii_lowercase[i] where i tracks position in the alphabet). Finally, it transforms each character in the message using this mapping dictionary.

Intuition

The key insight is recognizing this as a simple substitution cipher where we need to create a one-to-one mapping between characters.

When we look at the problem, we need to extract unique characters from the key in the order they first appear. This naturally suggests using a data structure that can track whether we've seen a character before - a dictionary or set would work well.

The mapping process itself is straightforward: we're essentially creating a translation table. Each unique character from the key needs to map to a letter in the standard alphabet ('a', 'b', 'c', ...). Since we need these mappings in order, we can use a counter variable that increments each time we encounter a new character.

Why use a dictionary? It gives us O(1) lookup time when decoding the message. As we build the dictionary while scanning through the key:

• We check if we've seen the character before (if c not in d)
• If it's new, we assign it the next available letter from the alphabet
• We can access the alphabet letters in order using ascii_lowercase[i] where i is our position counter

The special case of spaces is handled by pre-populating the dictionary with {" ": " "}, ensuring spaces map to themselves.

Once our mapping dictionary is complete, decoding the message becomes trivial - we just look up each character in our dictionary and join the results together. This gives us a clean, efficient solution that processes both the key and message in linear time.

Solution Approach

The solution implements a character mapping approach using a dictionary to create and apply the substitution cipher.

Step 1: Initialize the mapping dictionary

d = {" ": " "}

We start by creating a dictionary d with a single entry mapping space to space. This ensures spaces in the message remain unchanged during decoding.

Step 2: Build the substitution table from the key

i = 0
for c in key:
    if c not in d:
        d[c] = ascii_lowercase[i]
        i += 1

We iterate through each character c in the key string:

• Check if the character hasn't been seen before (c not in d)
• If it's a new character (and not a space), add it to the dictionary
• Map this character to the i-th letter of the alphabet using ascii_lowercase[i]
• Increment i to move to the next alphabet letter for the next unique character

This process captures only the first occurrence of each letter, automatically handling duplicates by skipping them.

Step 3: Decode the message

return "".join(d[c] for c in message)

Once the mapping dictionary is complete, we decode the message by:

• Iterating through each character c in the message
• Looking up each character in our dictionary d[c] to get its decoded value
• Using join() to combine all decoded characters into the final string

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) since the dictionary will contain at most 27 entries (26 letters + 1 space)

The elegance of this solution lies in using the dictionary both as a way to track seen characters and as the mapping table for decoding, eliminating the need for separate data structures.

Example Walkthrough

Let's trace through a complete example with key = "the quick brown fox" and message = "vkb".

Step 1: Initialize the mapping dictionary We start with d = {" ": " "} and i = 0.

Step 2: Build the substitution table from the key

Processing each character in "the quick brown fox":

• 't': Not in d, so d['t'] = 'a', increment i to 1
• 'h': Not in d, so d['h'] = 'b', increment i to 2
• 'e': Not in d, so d['e'] = 'c', increment i to 3
• ' ': Already in d (maps to space), skip
• 'q': Not in d, so d['q'] = 'd', increment i to 4
• 'u': Not in d, so d['u'] = 'e', increment i to 5
• 'i': Not in d, so d['i'] = 'f', increment i to 6
• 'c': Not in d, so d['c'] = 'g', increment i to 7
• 'k': Not in d, so d['k'] = 'h', increment i to 8
• ' ': Already in d, skip
• 'b': Not in d, so d['b'] = 'i', increment i to 9
• 'r': Not in d, so d['r'] = 'j', increment i to 10
• 'o': Not in d, so d['o'] = 'k', increment i to 11
• 'w': Not in d, so d['w'] = 'l', increment i to 12
• 'n': Not in d, so d['n'] = 'm', increment i to 13
• ' ': Already in d, skip
• 'f': Not in d, so d['f'] = 'n', increment i to 14
• 'o': Already in d (maps to 'k'), skip
• 'x': Not in d, so d['x'] = 'o', increment i to 15

Our final dictionary contains:

{' ': ' ', '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'}

Step 3: Decode the message "vkb"

Wait - 'v' is not in our key! For this example to work properly, let's use message = "the" instead:

• 't' → look up d['t'] → 'a'
• 'h' → look up d['h'] → 'b'
• 'e' → look up d['e'] → 'c'

Result: "abc"

The beauty of this approach is that we process the key only once to build our mapping, then decoding any message is just a simple lookup operation for each character.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m) where n is the length of the key string and m is the length of the message string.

• Iterating through the key string to build the mapping dictionary takes O(n) time, as we visit each character once
• Building the decoded message by iterating through the message string and looking up each character in the dictionary takes O(m) time, since dictionary lookup is O(1) on average
• The join operation also takes O(m) time as it needs to concatenate m characters
• Total time complexity: O(n) + O(m) = O(n + m)

Space Complexity: O(1) or O(26) to be precise, which simplifies to O(1).

• The dictionary d stores at most 26 lowercase letters plus the space character, giving us a maximum of 27 entries regardless of input size
• The output string requires O(m) space, but this is typically not counted as part of space complexity since it's the required output
• Since the dictionary size is bounded by a constant (27), the auxiliary space complexity is O(1)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Spaces Correctly

One of the most common mistakes is forgetting that spaces in the message should remain as spaces. If you don't explicitly handle spaces in your mapping, the code will crash with a KeyError when trying to decode a message containing spaces.

Incorrect approach:

char_mapping = {}  # Missing space mapping
for char in key:
    if char != " " and char not in char_mapping:
        char_mapping[char] = ascii_lowercase[alphabet_index]
        alphabet_index += 1
# This will fail when message contains spaces!

Correct approach:

char_mapping = {" ": " "}  # Initialize with space mapping

2. Processing Spaces from the Key

Another pitfall is accidentally treating spaces in the key as characters to be mapped to the alphabet. This would incorrectly advance the alphabet index and create wrong mappings for subsequent characters.

Incorrect approach:

for char in key:
    if char not in char_mapping:  # This would map space to 'a'!
        char_mapping[char] = ascii_lowercase[alphabet_index]
        alphabet_index += 1

Correct approach:

for char in key:
    if char != " " and char not in char_mapping:
        char_mapping[char] = ascii_lowercase[alphabet_index]
        alphabet_index += 1

3. Incomplete Alphabet Mapping

While not always necessary for the given message, some implementations might need to handle characters in the message that don't appear in the key. The problem statement guarantees this won't happen, but in a more general cipher implementation, you'd need to complete the mapping.

More robust approach for general use:

# After processing the key, add remaining unmapped letters
remaining_letters = [c for c in ascii_lowercase if c not in char_mapping.values()]
for letter in ascii_lowercase:
    if letter not in char_mapping and alphabet_index < 26:
        char_mapping[letter] = remaining_letters.pop(0)

4. String Concatenation in Loop

Using string concatenation in a loop is inefficient in Python. While it works, it creates a new string object for each concatenation.

Inefficient approach:

result = ""
for char in message:
    result += char_mapping[char]  # Creates new string each time

Efficient approach:

return "".join(char_mapping[char] for char in message)