Skip to main content
Talentd

Encrypt and Decrypt Strings - Solution & Explanation

HardArrayHash TableStringDesign15 min readAsked at: Amazon, Google, Duolingo
Practice this problem

Problem Statement

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:

  1. For each character c in the string, we find the index i satisfying keys[i] == c in keys.
  2. 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:

  1. 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.
  2. 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.

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.

Code

PythonJava

Python

Java

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.

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.

Code

C++JavaScript

C++

JavaScript

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 TrieEncrypt: O(n), Decrypt: O(branch^k) with pruningO(D * L)Best when decrypt is called frequently and dictionary words share common prefixes.

Video Solution

Encrypt and Decrypt Strings | Leetcode 2227 | Range Based Binary Search | Contest 287 🔥🔥 • Coding Decoded • 1,856 views views

Watch 8 more video solutions →

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.

Ready to solve this problem?

Practice Encrypt and Decrypt Strings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find the Sum of Encrypted Integers

Next

Implement Trie II (Prefix Tree)