Scale Engineer

Decode the Message

Easy
#2118Time: 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.2 companies
Data structures
Hash TableString
Companies
TeslaCoinbase

Prompt

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:

  1. Use the first appearance of all 26 lowercase English letters in key as the order of the substitution table.
  2. Align the substitution table with the regular English alphabet.
  3. Each letter in message is then substituted using the table.
  4. 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 <= 2000
  • key consists of lowercase English letters and ' '.
  • key contains every letter in the English alphabet ('a' to 'z') at least once.
  • 1 <= message.length <= 2000
  • message consists 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 key string. For each character c:
    • If c is a letter and not already in the map, add the mapping (c, currentChar) and increment currentChar.
  • Initialize an empty string, decodedMessage.
  • Iterate through the message string. For each character m:
    • If m is a space, append a space to decodedMessage using the += operator.
    • Otherwise, look up the substitution for m in the map and append it to decodedMessage using +=.
  • 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 OutOfMemoryError for long messages due to the creation of many intermediate string objects.

Solutions

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);  }}

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.

← Previous

Previous problem

Next →

Next problem