Decode the Message - Video Solutions

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.