You are given the strings key and message, which represent a cipher key and a secret message, respectively. The steps to decode message are as follows:
key as the order of the substitution table.message is then substituted using the table.' ' are transformed to themselves.key = "happy boy" (actual key would have at least one instance of each letter in the alphabet), we have the partial substitution table of ('h' -> 'a', 'a' -> 'b', 'p' -> 'c', 'y' -> 'd', 'b' -> 'e', 'o' -> 'f').Return the decoded message.
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 diagram above shows the substitution table. It is obtained by taking the first appearance of each letter in "the quick brown fox jumps over the lazy dog".
Example 2:
Input: key = "eljuxhpwnyrdgtqkviszcfmabo", message = "zwx hnfx lqantp mnoeius ycgk vcnjrdb" Output: "the five boxing wizards jump quickly" Explanation: The diagram above shows the substitution table. It is obtained by taking the first appearance of each letter in "eljuxhpwnyrdgtqkviszcfmabo".
Constraints:
26 <= key.length <= 2000key consists of lowercase English letters and ' '.key contains every letter in the English alphabet ('a' to 'z') at least once.1 <= message.length <= 2000message consists of lowercase English letters and ' '.In #2325 Decode the Message, you are given a key that represents a substitution cipher where the first appearance of each letter corresponds to the normal alphabet order (a to z). The goal is to use this mapping to decode the provided message.
A practical approach is to iterate through the key and build a hash table (or fixed-size array) that maps each unique character to the next available character in the alphabet. Spaces in the key are ignored, and only the first occurrence of each letter is considered. Once the mapping is created, iterate through the message and replace each character using the constructed mapping while preserving spaces.
This method ensures efficient decoding because each character lookup in the hash table is constant time. The algorithm processes the key once and the message once, making it highly efficient. The overall complexity is linear with respect to the combined length of the key and the message, with minimal extra space for the mapping structure.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Table Mapping from Key | O(n + m) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Iterate through the characters in the key to construct a mapping to the English alphabet.
Make sure to check that the current character is not already in the mapping (only the first appearance is considered).
Map the characters in the message according to the constructed mapping.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems like Decode the Message appear in coding interviews to test understanding of hash tables, string manipulation, and mapping logic. While the exact question may vary, similar substitution or mapping-based string problems are common in technical interviews.
A hash table or a fixed-size array of length 26 works best for this problem. It allows constant-time lookup when decoding each character in the message and makes the implementation straightforward.
The optimal approach is to build a substitution mapping using a hash table by scanning the key and assigning characters sequentially from 'a' to 'z'. After creating this mapping, iterate through the message and replace each character accordingly. This keeps decoding simple and efficient.
The cipher mapping is determined by the order of first appearance of each letter in the key. Once a character is mapped to a letter in the alphabet, later occurrences should be ignored to preserve the substitution order.