Decode the Message
EasyPrompt
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:
- Use the first appearance of all 26 lowercase English letters in
keyas the order of the substitution table. - Align the substitution table with the regular English alphabet.
- Each letter in
messageis then substituted using the table. - Spaces
' 'are transformed to themselves.
- For example, given
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 <= 2000keyconsists of lowercase English letters and' '.keycontains every letter in the English alphabet ('a'to'z') at least once.1 <= message.length <= 2000messageconsists of lowercase English letters and' '.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach first constructs the substitution table using a HashMap and then decodes the message. The key idea is to map the first occurrence of each character in the key string to the letters of the alphabet in order. However, it uses a suboptimal method for building the final decoded string by repeatedly concatenating to a String object.
Algorithm
- Initialize a
HashMap<Character, Character>to store the substitution mappings. - Initialize a character variable,
currentChar, to 'a'. - Iterate through the
keystring. For each characterc:- If
cis a letter and not already in the map, add the mapping(c, currentChar)and incrementcurrentChar.
- If
- Initialize an empty string,
decodedMessage. - Iterate through the
messagestring. For each characterm:- If
mis a space, append a space todecodedMessageusing the+=operator. - Otherwise, look up the substitution for
min the map and append it todecodedMessageusing+=.
- If
- Return
decodedMessage.
Walkthrough
The core of this method involves two main steps: creating the substitution table and decoding the message.
Substitution Table Creation:
A HashMap<Character, Character> is used to store the substitution mappings. We iterate through the key string. A separate character variable, say currentChar, is initialized to 'a' and acts as the value in our mapping. For each character c from the key, if it's a letter and not already in our map, we add the mapping (c, currentChar) to the map and increment currentChar. We skip spaces and duplicate letters.
Message Decoding:
An empty string decodedMessage is initialized. We then iterate through the message string. For each character m in the message, if m is a space, a space is appended to decodedMessage. Otherwise, we look up the corresponding decoded character from our map and append it. The critical flaw here is using the += operator for string concatenation inside a loop. In Java, strings are immutable. Each concatenation creates a new StringBuilder, appends the characters, and then creates a new String object, leading to quadratic time complexity relative to the message length.
Complexity
Time
O(K + M^2), where `K` is the length of the `key` and `M` is the length of the `message`. Building the map takes `O(K)`. Decoding the message takes `O(M^2)` because string concatenation in a loop in Java has quadratic complexity.
Space
O(M^2), where M is the length of the message. The `HashMap` uses O(1) space (as it stores at most 26 mappings). However, the repeated creation of new string objects during concatenation can lead to quadratic space usage for intermediate strings in the worst case.
Trade-offs
Pros
The logic is straightforward and easy to understand for beginners.
Cons
Highly inefficient due to the use of string concatenation (
+=) in a loop, which has quadratic time complexity in Java.Can lead to
OutOfMemoryErrorfor long messages due to the creation of many intermediate string objects.
This approach improves upon the previous one by using a StringBuilder for efficient string construction. It still uses a HashMap to create the substitution table, which is a standard and readable way to handle key-value mappings. This combination results in an efficient, linear-time solution.
Algorithm
- Initialize a
HashMap<Character, Character>to store the substitution mappings. - Initialize a character variable,
currentChar, to 'a'. - Iterate through the
keystring. For each characterc:- If
cis a letter and not already in the map, add the mapping(c, currentChar)and incrementcurrentChar.
- If
- Initialize a
StringBuilder. - Iterate through the
messagestring. For each characterm:- If
mis a space, append a space to theStringBuilder. - Otherwise, look up the substitution for
min the map and append it to theStringBuilder.
- If
- Convert the
StringBuilderto a string and return it.
Walkthrough
This method refines the decoding process for better performance.
Substitution Table Creation:
This part is identical to the previous approach. A HashMap<Character, Character> is created. We iterate through the key string, populating the map with the first occurrence of each letter, mapping it to the alphabet sequentially ('a', 'b', 'c', ...).
Message Decoding:
A StringBuilder is initialized to build the result string. We iterate through the message string. For each character m, if it's a space, we append a space to the StringBuilder; if it's a letter, we find its substitution in the HashMap and append the result. Using StringBuilder.append() is an O(1) amortized operation, making the entire decoding process linear in time. Finally, we convert the StringBuilder to a String and return it.
import java.util.HashMap;import java.util.Map; class Solution { public String decodeMessage(String key, String message) { Map<Character, Character> substitutionMap = new HashMap<>(); char currentChar = 'a'; for (char c : key.toCharArray()) { if (c != ' ' && !substitutionMap.containsKey(c)) { substitutionMap.put(c, currentChar++); } } StringBuilder decodedMessage = new StringBuilder(message.length()); for (char c : message.toCharArray()) { if (c == ' ') { decodedMessage.append(' '); } else { decodedMessage.append(substitutionMap.get(c)); } } return decodedMessage.toString(); }}Complexity
Time
O(K + M), where `K` is the length of the `key` and `M` is the length of the `message`. Building the map takes `O(K)` time. Decoding the message takes `O(M)` time because `StringBuilder.append()` is an amortized O(1) operation.
Space
O(M). The `HashMap` uses `O(1)` auxiliary space (at most 26 entries). The primary space usage comes from the `StringBuilder` which requires `O(M)` space to store the decoded message.
Trade-offs
Pros
Efficient, with optimal linear time complexity.
HashMapis a very readable and idiomatic way to represent arbitrary mappings.Handles the problem constraints effectively.
Cons
Incurs a slight overhead associated with
HashMap(e.g., hashing, memory for map entries) compared to a simple array.
This is the most optimized approach. It replaces the HashMap with a simple array of characters to serve as the substitution map. Since the keys are guaranteed to be lowercase English letters, an array is a perfect fit and offers the best performance for this specific use case by leveraging direct memory access.
Algorithm
- Initialize a
chararray of size 26,substitutionMap, with a default value (e.g.,\0). - Initialize a character variable,
currentChar, to 'a'. - Iterate through the
keystring. For each characterc:- If
cis a letter andsubstitutionMap[c - 'a']is still the default value, setsubstitutionMap[c - 'a']tocurrentCharand incrementcurrentChar.
- If
- Initialize a
StringBuilder. - Iterate through the
messagestring. For each characterm:- If
mis a space, append a space to theStringBuilder. - Otherwise, find the decoded character at
substitutionMap[m - 'a']and append it.
- If
- Convert the
StringBuilderto a string and return it.
Walkthrough
This approach maximizes performance by using the most suitable data structure for the given constraints.
Substitution Table Creation:
We use a char array of size 26, say substitutionMap, to store the mappings. The index of the array corresponds to a letter (e.g., index 0 for 'a', 1 for 'b', etc., via the calculation c - 'a'). The array is implicitly initialized with a sentinel value (the null character \0, which has a numeric value of 0). We iterate through the key string. For each character c, if it's a letter and the corresponding entry substitutionMap[c - 'a'] is still the sentinel value, we set substitutionMap[c - 'a'] to the next alphabet character and then increment our alphabet tracker.
Message Decoding:
This part is identical to the previous efficient approach. A StringBuilder is used for constructing the output string. We iterate through the message. For a letter m, the decoded character is found instantly at substitutionMap[m - 'a']. Spaces are handled as a special case.
class Solution { public String decodeMessage(String key, String message) { char[] substitutionMap = new char[26]; char currentChar = 'a'; for (char c : key.toCharArray()) { if (c != ' ' && substitutionMap[c - 'a'] == 0) { // char array default is '\0' which is 0 substitutionMap[c - 'a'] = currentChar++; } } StringBuilder decodedMessage = new StringBuilder(message.length()); for (char c : message.toCharArray()) { if (c == ' ') { decodedMessage.append(' '); } else { decodedMessage.append(substitutionMap[c - 'a']); } } return decodedMessage.toString(); }}Complexity
Time
O(K + M), where `K` is the length of the `key` and `M` is the length of the `message`. Both building the map and decoding the message are linear operations with O(1) lookups/updates in the array.
Space
O(M). The `substitutionMap` array uses `O(26)` which is `O(1)` auxiliary space. The `StringBuilder` requires `O(M)` space for the output.
Trade-offs
Pros
Most performant approach due to direct array indexing, which avoids the overhead of hashing and object creation associated with
HashMap.Minimal memory footprint for the substitution table.
Optimal time and space complexity.
Cons
This approach is slightly less generic than using a
HashMap; it works perfectly here because the keys are constrained to a small, contiguous set of characters ('a'-'z').
Solutions
Solution
class Solution {public String decodeMessage(String key, String message) { char[] d = new char[128]; d[' '] = ' '; for (int i = 0, j = 0; i < key.length(); ++i) { char c = key.charAt(i); if (d[c] == 0) { d[c] = (char)('a' + j++); } } char[] ans = message.toCharArray(); for (int i = 0; i < ans.length; ++i) { ans[i] = d[ans[i]]; } return String.valueOf(ans); }}class Solution {public: string decodeMessage(string key, string message) { char d[128]{}; d[' '] = ' '; char i = 'a'; for (char &c : key) { if (!d[c]) { d[c] = i++; } } for (char &c : message) { c = d[c]; } return message; }};class Solution: def decodeMessage(self, key: str, message: str) -> str: d = {" ": " "} i = 0 for c in key: if c not in d: d[c] = ascii_lowercase[i] i += 1 return "" . join(d[c] for c in message)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.