2227. Encrypt and Decrypt Strings Solution

Q: Is Encrypt and Decrypt Strings easy or hard?

Encrypt and Decrypt Strings is classified as a Hard problem because it combines API design with efficient preprocessing for repeated queries. Candidates must balance hashing, dictionary lookups, and Trie traversal to handle ambiguous decryptions efficiently.

Q: Encrypt and Decrypt Strings Python/Java solution

In Python or Java, the encryption mapping is typically stored in a dictionary or HashMap. Encryption iterates over the input string and appends mapped values. For optimized decryption, either store encrypted dictionary counts in a map or traverse a Trie using reverse mappings for each two-character segment.

Q: How to solve Encrypt and Decrypt Strings in O(n)?

Encryption itself is O(n) using a hash map from character to encrypted string. Each character is processed once and appended to the result. Decryption cannot be strictly O(n) in the worst case because multiple characters may map to the same encrypted pair, but Trie pruning keeps the search efficient in practice.

Q: What is the best approach for Encrypt and Decrypt Strings?

The most practical approach preprocesses the dictionary using a Trie and a reverse mapping from encrypted value to possible characters. Encryption becomes a simple hash lookup per character, while decryption explores only dictionary-valid prefixes through the Trie. This significantly reduces unnecessary checks compared with scanning the entire dictionary.

Q: Is Encrypt and Decrypt Strings asked at Google/Amazon/Meta?

Design-style problems combining hash tables, strings, and Trie structures commonly appear in interviews at companies like Google, Amazon, and Meta. This problem specifically tests system design thinking for APIs along with efficient data structure usage for repeated queries.

Q: What data structure is used in Encrypt and Decrypt Strings?

The core structures are hash tables for character-to-string encryption mapping and reverse lookup, plus a Trie to store dictionary words. The Trie allows efficient prefix validation while exploring possible decryptions. Strings and arrays are also used to process encrypted pairs.

Q: What is the time complexity of Encrypt and Decrypt Strings?

Encryption runs in O(n) time where n is the length of the input word because each character is mapped using a constant-time lookup. In the naive approach, decryption takes O(D * L) where D is the number of dictionary words and L is their average length. The Trie-based approach reduces practical runtime by pruning invalid prefixes during search.

The problem

You are given a character array keys containing unique characters and a string array values containing strings of length 2. You are also given another string array dictionary that contains all permitted original strings after decryption. You should implement a data structure that can encrypt or decrypt a 0-indexed string.

A string is encrypted with the following process:

For each character c in the string, we find the index i satisfying keys[i] == c in keys.
Replace c with values[i] in the string.

Note that in case a character of the string is not present in keys, the encryption process cannot be carried out, and an empty string "" is returned.

A string is decrypted with the following process:

For each substring s of length 2 occurring at an even index in the string, we find an i such that values[i] == s. If there are multiple valid i, we choose any one of them. This means a string could have multiple possible strings it can decrypt to.
Replace s with keys[i] in the string.

Implement the Encrypter class:

Encrypter(char[] keys, String[] values, String[] dictionary) Initializes the Encrypter class with keys, values, and dictionary.
String encrypt(String word1) Encrypts word1 with the encryption process described above and returns the encrypted string.
int decrypt(String word2) Returns the number of possible strings word2 could decrypt to that also appear in dictionary.

Example 1:

Input
["Encrypter", "encrypt", "decrypt"]
[[['a', 'b', 'c', 'd'], ["ei", "zf", "ei", "am"], ["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"]], ["abcd"], ["eizfeiam"]]
Output
[null, "eizfeiam", 2]

Explanation
Encrypter encrypter = new Encrypter([['a', 'b', 'c', 'd'], ["ei", "zf", "ei", "am"], ["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"]);
encrypter.encrypt("abcd"); // return "eizfeiam". 
                           // 'a' maps to "ei", 'b' maps to "zf", 'c' maps to "ei", and 'd' maps to "am".
encrypter.decrypt("eizfeiam"); // return 2. 
                              // "ei" can map to 'a' or 'c', "zf" maps to 'b', and "am" maps to 'd'. 
                              // Thus, the possible strings after decryption are "abad", "cbad", "abcd", and "cbcd". 
                              // 2 of those strings, "abad" and "abcd", appear in dictionary, so the answer is 2.

Constraints:

1 <= keys.length == values.length <= 26
values[i].length == 2
1 <= dictionary.length <= 100
1 <= dictionary[i].length <= 100
All keys[i] and dictionary[i] are unique.
1 <= word1.length <= 2000
2 <= word2.length <= 200
All word1[i] appear in keys.
word2.length is even.
keys, values[i], dictionary[i], word1, and word2 only contain lowercase English letters.
At most 200 calls will be made to encrypt and decrypt in total.

Approach overview

Problem Overview: Design a class that encrypts a word by mapping each character to a fixed two‑character string, and decrypts an encrypted string by counting how many words from a dictionary could produce it.

Approach 1: Direct Mapping Approach (Hash Map + Dictionary Scan) (Encrypt: O(n), Decrypt: O(D * L))

Store a char → string mapping in a hash table for fast encryption. Encryption is straightforward: iterate through the input string, look up each character in the map, and append the mapped value. For decryption, iterate through every word in the dictionary, encrypt it using the same mapping, and compare the result with the encrypted query string. This works because the dictionary size is limited, but it can be expensive when many dictionary words must be re‑encrypted for each query.

Approach 2: Preprocessed Decryption Using Trie (O(n) encrypt, O(branch^k) decrypt with pruning)

Instead of re‑encrypting the dictionary every time, preprocess it. Build a reverse mapping from encrypted value → possible characters, then insert all dictionary words into a Trie. During decryption, process the encrypted string in 2‑character chunks. For each chunk, use the reverse map to find all candidate characters, then traverse the Trie to check whether those characters can continue a valid dictionary word. The Trie prunes invalid paths early, so you only explore prefixes that actually exist in the dictionary.

This approach shifts work to preprocessing. Encryption still performs a simple lookup per character, but decryption becomes a guided search constrained by the dictionary structure. In practice it avoids recomputing encrypted forms and drastically reduces unnecessary comparisons.

Recommended for interviews: Start with the direct hash‑map mapping to show you understand the encryption rule and dictionary validation. Then move to the Trie‑based preprocessing solution. Interviewers expect candidates to recognize that naive dictionary scanning repeats work and that building a Trie allows efficient prefix pruning during decryption.

Approach 1: Direct Mapping Approach

This approach uses direct mapping for both encryption and decryption. We maintain a dictionary for fast lookup. For encryption, we map each character to its corresponding encrypted string. For decryption, we have to handle potential multiple mappings by considering each possibility in sequence. This is done using a dictionary to quickly reference mappings.

Python

class Encrypter:
    def __init__(self, keys, values, dictionary):
        self.char_to_encrypted = {keys[i]: values[i] for i in range(len(keys))}
        self.encrypted_to_chars = {}
        for i in range(len(keys)):
            if values[i] not in self.encrypted_to_chars:
                self.encrypted_to_chars[values[i]] = []
            self.encrypted_to_chars[values[i]].append(keys[i])
        self.dictionary = set(dictionary)

    def encrypt(self, word1):
        try:
            return ''.join(self.char_to_encrypted[c] for c in word1)
        except KeyError:
            return ""

    def decrypt(self, word2):
        def backtrack(index, current):
            if index == len(word2):
                return 1 if current in self.dictionary else 0

            pair = word2[index:index+2]
            if pair in self.encrypted_to_chars:
                count = 0
                for ch in self.encrypted_to_chars[pair]:
                    count += backtrack(index+2, current + ch)
                return count
            return 0

        return backtrack(0, '')

Java

class Encrypter {
    private Map<Character, String> charToEncrypted;
    private Map<String, List<Character>> encryptedToChars;
    private Set<String> dictionarySet;

    public Encrypter(char[] keys, String[] values, String[] dictionary) {
        charToEncrypted = new HashMap<>();
        encryptedToChars = new HashMap<>();
        for (int i = 0; i < keys.length; i++) {
            charToEncrypted.put(keys[i], values[i]);
            encryptedToChars.computeIfAbsent(values[i], k -> new ArrayList<>()).add(keys[i]);
        }
        dictionarySet = new HashSet<>(Arrays.asList(dictionary));
    }

    public String encrypt(String word1) {
        StringBuilder sb = new StringBuilder();
        for (char c : word1.toCharArray()) {
            if (!charToEncrypted.containsKey(c)) return "";
            sb.append(charToEncrypted.get(c));
        }
        return sb.toString();
    }

    public int decrypt(String word2) {
        return decryptHelper(word2, 0, new StringBuilder());
    }

    private int decryptHelper(String word2, int index, StringBuilder current) {
        if (index == word2.length()) {
            return dictionarySet.contains(current.toString()) ? 1 : 0;
        }

        String pair = word2.substring(index, index + 2);
        int count = 0;
        if (encryptedToChars.containsKey(pair)) {
            for (char c : encryptedToChars.get(pair)) {
                current.append(c);
                count += decryptHelper(word2, index + 2, current);
                current.deleteCharAt(current.length() - 1);
            }
        }
        return count;
    }
}

The Encrypter class uses dictionaries: char_to_encrypted for quick encryption lookups and encrypted_to_chars to map encrypted sub-strings back to possible characters for decryption. Encryption builds a string by replacing each character with its encrypted version. Decryption uses backtracking to test all possible decryptions against the dictionary.

Complexity

Time Complexity: Encryption is O(n), where n is the length of the string. Decryption is exponential in the worst case, depending on the number of valid decryption branches.
Space Complexity: O(k + m) for storing mappings and dictionary, where k is the number of keys and m is the size of the dictionary.

Try this approach in the editor

Approach 2: Preprocessed Decryption Approach Using Trie

Instead of brute forcing for all possible decryptions, this approach preprocesses the dictionary strings into a Trie structure which allows efficient look-up of potential matches during decryption. This approach attempts to leverage the prefix nature of the Trie to cut down unnecessary branches of exploration.

C++

#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <string>
using namespace std;

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isEndOfWord;
    TrieNode() : isEndOfWord(false) {}
};

class Encrypter {
    unordered_map<char, string> charToEncrypted;
    unordered_map<string, vector<char>> encryptedToChars;
    TrieNode* root;

    void insertToTrie(const string& word) {
        TrieNode* node = root;
        for (char letter : word) {
            if (!node->children.count(letter))
                node->children[letter] = new TrieNode();
            node = node->children[letter];
        }
        node->isEndOfWord = true;
    }

public:
    Encrypter(vector<char> keys, vector<string> values, vector<string> dictionary) {
        for (int i = 0; i < keys.size(); i++) {
            charToEncrypted[keys[i]] = values[i];
            encryptedToChars[values[i]].push_back(keys[i]);
        }
        root = new TrieNode();
        for (const string& word : dictionary) {
            insertToTrie(word);
        }
    }

    string encrypt(string word1) {
        string result;
        for (char c : word1) {
            if (charToEncrypted.count(c) == 0) return "";
            result += charToEncrypted[c];
        }
        return result;
    }

    int decrypt(string word2) {
        return decryptHelper(word2, 0, root);
    }

    int decryptHelper(const string& word2, int index, TrieNode* node) {
        if (index == word2.length()) {
            return node->isEndOfWord ? 1 : 0;
        }

        string pair = word2.substr(index, 2);
        if (!encryptedToChars.count(pair)) return 0;

        int count = 0;
        for (char c : encryptedToChars[pair]) {
            if (node->children.count(c) > 0) {
                count += decryptHelper(word2, index + 2, node->children[c]);
            }
        }
        return count;
    }
};

JavaScript

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

class Encrypter {
    constructor(keys, values, dictionary) {
        this.charToEncrypted = new Map();
        this.encryptedToChars = new Map();
        for (let i = 0; i < keys.length; i++) {
            this.charToEncrypted.set(keys[i], values[i]);
            if (!this.encryptedToChars.has(values[i])) {
                this.encryptedToChars.set(values[i], []);
            }
            this.encryptedToChars.get(values[i]).push(keys[i]);
        }
        this.root = new TrieNode();
        dictionary.forEach(word => this.insertToTrie(word));
    }

    insertToTrie(word) {
        let node = this.root;
        for (let letter of word) {
            if (!node.children[letter]) {
                node.children[letter] = new TrieNode();
            }
            node = node.children[letter];
        }
        node.isEndOfWord = true;
    }

    encrypt(word1) {
        let result = '';
        for (let c of word1) {
            if (!this.charToEncrypted.has(c)) return '';
            result += this.charToEncrypted.get(c);
        }
        return result;
    }

    decrypt(word2) {
        return this.decryptHelper(word2, 0, this.root);
    }

    decryptHelper(word2, index, node) {
        if (index === word2.length) {
            return node.isEndOfWord ? 1 : 0;
        }

        let pair = word2.substr(index, 2);
        if (!this.encryptedToChars.has(pair)) return 0;

        let count = 0;
        for (let c of this.encryptedToChars.get(pair)) {
            if (node.children[c]) {
                count += this.decryptHelper(word2, index + 2, node.children[c]);
            }
        }
        return count;
    }
}

This C++ solution uses a Trie to store the dictionary for quick lookup. The encryption process is similar to the previous method, however, the decryption leverages the Trie data structure to efficiently count valid dictionary words as it builds potential decryptions by recursively exploring the Trie based on encrypted pairs.

Complexity

Time Complexity: O(n) for encryption and approximately O(2^m) for decryption in the worst case, where m is the length of word2. The Trie optimizes search by pruning non-matching prefixes.
Space Complexity: O(k + m * l), where l is the average length of dictionary words.

Try this approach in the editor

Approach 3: Hash Table

We use a hash table mp to record the encryption result of each character, and another hash table cnt to record the number of occurrences of each encryption result.

In the constructor, we traverse keys and values, storing each character and its corresponding encryption result in mp. Then, we traverse dictionary to count the occurrences of each encryption result. The time complexity is O(n + m), where n and m are the lengths of keys and dictionary, respectively.

In the encryption function, we traverse each character of the input string word1, look up its encryption result, and concatenate them. If a character does not have a corresponding encryption result, it means encryption is not possible, and we return an empty string. The time complexity is O(k), where k is the length of word1.

In the decryption function, we directly return the count of word2 in cnt. The time complexity is O(1).

The space complexity is O(n + m).

TypeScript

class Encrypter {
    private mp: Map<string, string> = new Map();
    private cnt: Map<string, number> = new Map();

    constructor(keys: string[], values: string[], dictionary: string[]) {
        for (let i = 0; i < keys.length; i++) {
            this.mp.set(keys[i], values[i]);
        }
        for (const w of dictionary) {
            const encrypted = this.encrypt(w);
            if (encrypted !== '') {
                this.cnt.set(encrypted, (this.cnt.get(encrypted) || 0) + 1);
            }
        }
    }

    encrypt(word: string): string {
        let res = '';
        for (const c of word) {
            if (!this.mp.has(c)) {
                return '';
            }
            res += this.mp.get(c);
        }
        return res;
    }

    decrypt(word: string): number {
        return this.cnt.get(word) || 0;
    }
}

/**
 * Your Encrypter object will be instantiated and called as such:
 * const obj = new Encrypter(keys, values, dictionary);
 * const param_1 = obj.encrypt(word1);
 * const param_2 = obj.decrypt(word2);
 */

type Encrypter struct {
	mp  map[byte]string
	cnt map[string]int
}

func Constructor(keys []byte, values []string, dictionary []string) Encrypter {
	mp := map[byte]string{}
	cnt := map[string]int{}
	for i, k := range keys {
		mp[k] = values[i]
	}
	e := Encrypter{mp, cnt}
	for _, v := range dictionary {
		e.cnt[e.Encrypt(v)]++
	}
	return e
}

func (this *Encrypter) Encrypt(word1 string) string {
	var ans strings.Builder
	for _, c := range word1 {
		if v, ok := this.mp[byte(c)]; ok {
			ans.WriteString(v)
		} else {
			return ""
		}
	}
	return ans.String()
}

func (this *Encrypter) Decrypt(word2 string) int {
	return this.cnt[word2]
}

/**
 * Your Encrypter object will be instantiated and called as such:
 * obj := Constructor(keys, values, dictionary);
 * param_1 := obj.Encrypt(word1);
 * param_2 := obj.Decrypt(word2);
 */

Try this approach in the editor

Complexity comparison

Approach	Complexity
Direct Mapping Approach	Time Complexity: Encryption is O(n), where n is the length of the string. Decryption is exponential in the worst case, depending on the number of valid decryption branches. Space Complexity: O(k + m) for storing mappings and dictionary, where k is the number of keys and m is the size of the dictionary.
Preprocessed Decryption Approach Using Trie	Time Complexity: O(n) for encryption and approximately O(2^m) for decryption in the worst case, where m is the length of `word2`. The Trie optimizes search by pruning non-matching prefixes. Space Complexity: O(k + m * l), where l is the average length of dictionary words.
Hash Table	–

Complexity analysis

Approach	Time	Space	When to Use
Direct Mapping (Hash Map + Dictionary Scan)	Encrypt: O(n), Decrypt: O(D * L)	O(K + D)	Simple implementation when dictionary size is small and decrypt calls are limited.
Preprocessed Decryption Using Trie	Encrypt: O(n), Decrypt: O(branch^k) with pruning	O(D * L)	Best when decrypt is called frequently and dictionary words share common prefixes.

Frequently asked questions

Is Encrypt and Decrypt Strings easy or hard?

Encrypt and Decrypt Strings is classified as a Hard problem because it combines API design with efficient preprocessing for repeated queries. Candidates must balance hashing, dictionary lookups, and Trie traversal to handle ambiguous decryptions efficiently.

Encrypt and Decrypt Strings Python/Java solution

In Python or Java, the encryption mapping is typically stored in a dictionary or HashMap. Encryption iterates over the input string and appends mapped values. For optimized decryption, either store encrypted dictionary counts in a map or traverse a Trie using reverse mappings for each two-character segment.

How to solve Encrypt and Decrypt Strings in O(n)?

Encryption itself is O(n) using a hash map from character to encrypted string. Each character is processed once and appended to the result. Decryption cannot be strictly O(n) in the worst case because multiple characters may map to the same encrypted pair, but Trie pruning keeps the search efficient in practice.

What is the best approach for Encrypt and Decrypt Strings?

The most practical approach preprocesses the dictionary using a Trie and a reverse mapping from encrypted value to possible characters. Encryption becomes a simple hash lookup per character, while decryption explores only dictionary-valid prefixes through the Trie. This significantly reduces unnecessary checks compared with scanning the entire dictionary.

Is Encrypt and Decrypt Strings asked at Google/Amazon/Meta?

Design-style problems combining hash tables, strings, and Trie structures commonly appear in interviews at companies like Google, Amazon, and Meta. This problem specifically tests system design thinking for APIs along with efficient data structure usage for repeated queries.

What data structure is used in Encrypt and Decrypt Strings?

The core structures are hash tables for character-to-string encryption mapping and reverse lookup, plus a Trie to store dictionary words. The Trie allows efficient prefix validation while exploring possible decryptions. Strings and arrays are also used to process encrypted pairs.

What is the time complexity of Encrypt and Decrypt Strings?

Encryption runs in O(n) time where n is the length of the input word because each character is mapped using a constant-time lookup. In the naive approach, decryption takes O(D * L) where D is the number of dictionary words and L is their average length. The Trie-based approach reduces practical runtime by pruning invalid prefixes during search.

Encrypt and Decrypt Strings solution and explanation

The problem

Approach overview

Approach 1: Direct Mapping Approach

Approach 2: Preprocessed Decryption Approach Using Trie

Approach 3: Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Encrypt and Decrypt Strings solution and explanation

The problem

Approach overview

Approach 1: Direct Mapping Approach

Approach 2: Preprocessed Decryption Approach Using Trie

Approach 3: Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems