Decode the Message - Practice Coding Problems

Decode the Message - 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:

Use the first appearance of all 26 lowercase English letters in key as the order of the substitution table.
Align the substitution table with the regular English alphabet.
Each letter in message is 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.

Input & Output

Example 1 — Basic Substitution

$ Input: key = "the quick brown fox jumps over the lazy dog", message = "vkbs bs t suepuv"

› Output: this is a secret

💡 Note: Key contains all 26 letters. First unique chars: t→a, h→b, e→c, q→d, u→e, i→f, c→g, k→h, etc. Decoding 'v'→'s', 'k'→'h', 'b'→'i', 's'→'t' gives 'this is a secret'

Example 2 — With Spaces

$ Input: key = "happy boy", message = "h p"

› Output: a e

💡 Note: Key gives mapping h→a, a→b, p→c, y→d, b→e, o→f. Message 'h p' becomes 'a e' (spaces preserved)

Example 3 — Single Character

$ Input: key = "abcdefghijklmnopqrstuvwxyz", message = "z"

› Output: z

💡 Note: Key is regular alphabet, so z→z (26th letter maps to 26th position)

Constraints

1 ≤ key.length ≤ 10⁵
1 ≤ message.length ≤ 10⁴
key contains every letter of the English alphabet at least once
key and message consist of lowercase English letters and spaces

Visualization

Tap to expand

Understanding the Visualization

Extract Key

Get first occurrence of each letter from key string

Build Map

Map key characters to alphabet positions

Decode

Transform message using substitution table

Key Takeaway

🎯 Key Insight: Build a character mapping from the unique letters in key to alphabet positions for fast O(1) substitution

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is to build a substitution table by mapping the first occurrence of each unique character in the key to the regular alphabet order. The optimal approach uses a hash map for O(1) character lookup. Time: O(n+m), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Substitution	O(n + m)	O(1)	Build a hash map for O(1) character substitution lookup
Brute Force Character Lookup	O(n × m)	O(n)	For each character in message, find its position in the unique key characters

Hash Map Substitution — Algorithm Steps

Step 1: Extract unique characters from key in order
Step 2: Build hash map mapping each key char to alphabet char
Step 3: Use map to substitute each message character

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Map

Create hash map from key chars to alphabet chars

O(1) Lookup

Use map for instant character substitution

Fast Decode

Process entire message efficiently

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

char* solution(char* key, char* message) {
    // Build substitution map using array (since only lowercase letters)
    char charMap[26];
    bool mapped[26] = {false};
    int alphabetIdx = 0;
    
    // Initialize map
    for (int i = 0; i < 26; i++) {
        charMap[i] = 'a' + i; // default mapping
    }
    
    bool seen[26] = {false};
    for (int i = 0; key[i]; i++) {
        char c = key[i];
        if (c >= 'a' && c <= 'z' && !seen[c - 'a']) {
            charMap[c - 'a'] = 'a' + alphabetIdx;
            seen[c - 'a'] = true;
            mapped[c - 'a'] = true;
            alphabetIdx++;
        }
    }
    
    // Decode message using map
    int len = strlen(message);
    char* result = malloc(len + 1);
    int resultIdx = 0;
    
    for (int i = 0; message[i]; i++) {
        char c = message[i];
        if (c == ' ') {
            result[resultIdx++] = ' ';
        } else if (c >= 'a' && c <= 'z') {
            result[resultIdx++] = charMap[c - 'a'];
        } else {
            result[resultIdx++] = c;
        }
    }
    
    result[resultIdx] = '\0';
    return result;
}

int main() {
    char key[1000], message[1000];
    fgets(key, sizeof(key), stdin);
    key[strcspn(key, "\n")] = 0;
    fgets(message, sizeof(message), stdin);
    message[strcspn(message, "\n")] = 0;
    
    char* result = solution(key, message);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

Single pass through key (n chars) plus single pass through message (m chars)

✓ Linear Growth

Space Complexity

O(1)

Hash map stores at most 26 character mappings (constant space)

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Substitution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler