algoadvance

Leetcode 2325. Decode the Message

Problem Statement

Leetcode problem 2325: Decode the Message

You are given a string key and a string message.

The key is a permutation of the lowercase English letters (‘a’ to ‘z’) which is a way to ensure that each letter appears exactly once. The message is a string consisting of lowercase English letters and spaces.

You need to decode the message using the key such that each letter in the message is replaced by the corresponding letter in the alphabetical order (i.e., if a letter x maps to the 1st letter in the alphabet, it maps to ‘a’, if it maps to the 2nd letter in the alphabet, it maps to ‘b’, and so on).

Return the decoded message.

Clarifying Questions

  1. Are there any constraints on the length of the key and message?
    • The lengths of key and message are not explicitly limited, but key is always 26 characters long and message can be of any length.
  2. Should I take care of upper-case letters or other symbols?
    • No, the problem specifies only lowercase English letters and spaces.

Strategy

  1. Create a mapping from the permutation given in the key to the standard alphabetical order.
  2. Iterate through the message, use the mapping to construct the decoded message.
  3. For spaces in the message, append them directly to the decoded output.

Code

Here’s the Java code to solve the problem:

import java.util.HashMap;
import java.util.Map;

public class Decoder {
    public String decodeMessage(String key, String message) {
        // Step 1: Create the mapping from `key` to the standard alphabet
        Map<Character, Character> keyMap = new HashMap<>();
        
        char currentAlphabetChar = 'a';
        for (char ch : key.toCharArray()) {
            if (ch != ' ' && !keyMap.containsKey(ch)) {
                keyMap.put(ch, currentAlphabetChar++);
            }
        }
        
        // Step 2: Use the mapping to decode the message
        StringBuilder decodedMessage = new StringBuilder();
        for (char ch : message.toCharArray()) {
            if (ch != ' ') {
                decodedMessage.append(keyMap.get(ch));
            } else {
                decodedMessage.append(' ');
            }
        }
        
        return decodedMessage.toString();
    }

    public static void main(String[] args) {
        Decoder decoder = new Decoder();
        String key = "the quick brown fox jumps over lazy dog";
        String message = "vkbs bs t suepuv";
        System.out.println(decoder.decodeMessage(key, message));  // Expected Output: "this is a secret"
    }
}

Time Complexity

The time complexity of the solution is O(N), where N is the length of message because:

  1. Building the mapping from key requires a single pass through the key, which takes O(26) or O(1).
  2. Decoding the message requires a single pass through message, thus O(N).

Space Complexity

The space complexity is O(1) for the mapping table since it only stores mappings for a fixed set of 26 letters, resulting in a constant space requirement regardless of input size. The output space is O(N) for storing the decoded message.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI