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.

Examples

Example 1

1
2
3
4
5
6
7


![](https://assets.leetcode.com/uploads/2022/05/08/ex1new4.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

1
2
3
4
5
6
7


![](https://assets.leetcode.com/uploads/2022/05/08/ex2new.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 ' '.

Solution

Method 1 – Hash Map Substitution 1

Intuition

We can decode the message by building a mapping from the first appearance of each letter in the key to the regular English alphabet. Then, we substitute each character in the message using this mapping. This works because the key contains every letter at least once, so the mapping is always complete.

Approach

  1. Iterate through the key and record the first occurrence of each letter, mapping it to ‘a’, ‘b’, …, ‘z’.
  2. For each character in the message:
    • If it is a space, keep it as is.
    • Otherwise, substitute it using the mapping.
  3. Build and return the decoded message.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    string decodeMessage(string key, string message) {
        unordered_map<char, char> mp;
        char ch = 'a';
        for (char c : key) {
            if (c != ' ' && mp.find(c) == mp.end()) {
                mp[c] = ch++;
            }
        }
        string ans;
        for (char c : message) {
            ans += (c == ' ' ? ' ' : mp[c]);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func decodeMessage(key, message string) string {
    mp := make(map[byte]byte)
    ch := byte('a')
    for i := 0; i < len(key); i++ {
        c := key[i]
        if c != ' ' && mp[c] == 0 {
            mp[c] = ch
            ch++
        }
    }
    ans := make([]byte, len(message))
    for i := 0; i < len(message); i++ {
        if message[i] == ' ' {
            ans[i] = ' '
        } else {
            ans[i] = mp[message[i]]
        }
    }
    return string(ans)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public String decodeMessage(String key, String message) {
        Map<Character, Character> mp = new HashMap<>();
        char ch = 'a';
        for (char c : key.toCharArray()) {
            if (c != ' ' && !mp.containsKey(c)) {
                mp.put(c, ch++);
            }
        }
        StringBuilder ans = new StringBuilder();
        for (char c : message.toCharArray()) {
            ans.append(c == ' ' ? ' ' : mp.get(c));
        }
        return ans.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun decodeMessage(key: String, message: String): String {
        val mp = mutableMapOf<Char, Char>()
        var ch = 'a'
        for (c in key) {
            if (c != ' ' && mp[c] == null) {
                mp[c] = ch++
            }
        }
        val ans = StringBuilder()
        for (c in message) {
            ans.append(if (c == ' ') ' ' else mp[c])
        }
        return ans.toString()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def decodeMessage(self, key: str, message: str) -> str:
        mp: dict[str, str] = {}
        ch = ord('a')
        for c in key:
            if c != ' ' and c not in mp:
                mp[c] = chr(ch)
                ch += 1
        ans = []
        for c in message:
            ans.append(' ' if c == ' ' else mp[c])
        return ''.join(ans)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn decode_message(key: String, message: String) -> String {
        use std::collections::HashMap;
        let mut mp = HashMap::new();
        let mut ch = b'a';
        for c in key.bytes() {
            if c != b' ' && !mp.contains_key(&c) {
                mp.insert(c, ch);
                ch += 1;
            }
        }
        message.bytes().map(|c| {
            if c == b' ' { ' ' } else { mp[&c] as char }
        }).collect()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    decodeMessage(key: string, message: string): string {
        const mp: Record<string, string> = {};
        let ch = 97;
        for (const c of key) {
            if (c !== ' ' && !(c in mp)) {
                mp[c] = String.fromCharCode(ch++);
            }
        }
        let ans = '';
        for (const c of message) {
            ans += c === ' ' ? ' ' : mp[c];
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n + m), where n is the length of key and m is the length of message, as we scan both once.
  • 🧺 Space complexity: O(1), since the mapping size is constant (26 letters).