# Decode the Message
**Difficulty:** EASY
[External](https://leetcode.com/problems/decode-the-message)
Canonical: https://scaleengineer.com/dsa/problems/decode-the-message
**Data structures:** Hash Table, String
**Companies:** [Tesla](https://scaleengineer.com/companies/tesla), [Coinbase](https://scaleengineer.com/companies/coinbase)
---
## Problem
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 = "**hap**p**y** **bo**y"` (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:**

![](https://assets.glich.co/dsa/decode-the-message/image0.jpg) 

**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** **f**o**x** **j**u**mps** o**v**er the **lazy** **d**o**g**".

**Example 2:**

![](https://assets.glich.co/dsa/decode-the-message/image1.jpg) 

**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
## HashMap with Inefficient String Concatenation
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.
**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.
**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.
### Explanation
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.
### 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`.

## HashMap and StringBuilder
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.
**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.
**Pros:** Efficient, with optimal linear time complexity.; `HashMap` is 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.
### Explanation
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.
```java
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();
    }
}
```
### 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 a `StringBuilder`.
- Iterate through the `message` string. For each character `m`:
  - If `m` is a space, append a space to the `StringBuilder`.
  - Otherwise, look up the substitution for `m` in the map and append it to the `StringBuilder`.
- Convert the `StringBuilder` to a string and return it.

## Array-based Map and StringBuilder
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.
**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.
**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').
### Explanation
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.
```java
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();
    }
}
```
### Algorithm
- Initialize a `char` array of size 26, `substitutionMap`, with a default value (e.g., `\0`).
- Initialize a character variable, `currentChar`, to 'a'.
- Iterate through the `key` string. For each character `c`:
  - If `c` is a letter and `substitutionMap[c - 'a']` is still the default value, set `substitutionMap[c - 'a']` to `currentChar` and increment `currentChar`.
- Initialize a `StringBuilder`.
- Iterate through the `message` string. For each character `m`:
  - If `m` is a space, append a space to the `StringBuilder`.
  - Otherwise, find the decoded character at `substitutionMap[m - 'a']` and append it.
- Convert the `StringBuilder` to a string and return it.

# Solutions
### Java

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

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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)

```