# Encrypt and Decrypt Strings
**Difficulty:** HARD
[External](https://leetcode.com/problems/encrypt-and-decrypt-strings)
Canonical: https://scaleengineer.com/dsa/problems/encrypt-and-decrypt-strings
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Array, Hash Table, String, Trie
**Companies:** [Duolingo](https://scaleengineer.com/companies/duolingo)
---
## 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:

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

# Approaches
## Brute-Force Decryption with Backtracking
This approach directly implements the described logic. For encryption, it maps each character to its corresponding two-character string. For decryption, it generates all possible original strings for a given encrypted string and counts how many of them are present in the dictionary.
**Time:** O(M^(L_w2 / 2) * (L_w2 / 2)). The `decrypt` method has exponential time complexity, where `L_w2` is the length of `word2` and `M` is the maximum number of keys mapping to the same value. The constructor is `O(K + D * L_d)` and `encrypt` is `O(L_w1)`. · **Space:** O(K + D * L_d + L_w2). `O(K + D * L_d)` for the maps and set, where K is the number of keys, D is dictionary size, and L_d is average word length. `O(L_w2/2)` for the recursion stack in `decrypt`.
**Pros:** Conceptually straightforward implementation of the decryption process.; The `encrypt` method is efficient.
**Cons:** The `decrypt` method is extremely inefficient due to its exponential time complexity. It will likely time out on larger inputs.; Repeatedly generates all possible decryptions for each `decrypt` call, which is redundant if the same string is decrypted multiple times.
### Explanation
In this approach, we set up two maps during initialization: one for fast encryption (`char -> String`) and another for decryption (`String -> List<char>`). The dictionary is stored in a `HashSet` for quick lookups. The `encrypt` method is straightforward, simply building the encrypted string character by character. The main logic resides in the `decrypt` method, which uses a backtracking algorithm. This recursive function explores every possible decryption path. For each 2-character segment of the input `word2`, it tries all possible original characters from our decryption map. When a full potential decryption is formed, it's checked against the dictionary set. While this correctly implements the logic, the number of possible decryptions can grow exponentially, making this solution too slow for the given constraints.

```java
class Encrypter {
    private Map<Character, String> keyToValueMap = new HashMap<>();
    private Map<String, List<Character>> valueToKeysMap = new HashMap<>();
    private Set<String> dictionarySet = new HashSet<>();
    private int count;

    public Encrypter(char[] keys, String[] values, String[] dictionary) {
        for (int i = 0; i < keys.length; i++) {
            keyToValueMap.put(keys[i], values[i]);
            valueToKeysMap.computeIfAbsent(values[i], k -> new ArrayList<>()).add(keys[i]);
        }
        for (String word : dictionary) {
            dictionarySet.add(word);
        }
    }

    public String encrypt(String word1) {
        StringBuilder sb = new StringBuilder();
        for (char c : word1.toCharArray()) {
            sb.append(keyToValueMap.get(c));
        }
        return sb.toString();
    }

    public int decrypt(String word2) {
        count = 0;
        backtrack(word2, 0, new StringBuilder());
        return count;
    }

    private void backtrack(String word2, int index, StringBuilder currentDecryption) {
        if (index == word2.length()) {
            if (dictionarySet.contains(currentDecryption.toString())) {
                count++;
            }
            return;
        }

        String sub = word2.substring(index, index + 2);
        if (valueToKeysMap.containsKey(sub)) {
            for (char c : valueToKeysMap.get(sub)) {
                currentDecryption.append(c);
                backtrack(word2, index + 2, currentDecryption);
                currentDecryption.deleteCharAt(currentDecryption.length() - 1);
            }
        }
    }
}
```
### Algorithm
- **Initialization (`Encrypter` constructor):**
  - Create a `HashMap<Character, String>` (`keyToValueMap`) to store the `keys` to `values` mapping for efficient encryption lookups.
  - Create a `HashMap<String, List<Character>>` (`valueToKeysMap`) to store the reverse mapping from a 2-character string back to all possible original characters. This is needed for decryption.
  - Store the `dictionary` in a `HashSet<String>` for quick O(1) average time lookups.
- **Encryption (`encrypt` method):**
  - Given `word1`, iterate through its characters.
  - For each character, use `keyToValueMap` to find the corresponding encrypted string.
  - Append these encrypted strings to build the final result.
- **Decryption (`decrypt` method):**
  - Use a recursive backtracking function to explore all possible decryptions of `word2`.
  - The function takes the current index in `word2` and the partially built decrypted string.
  - In each step, it considers the next 2-character substring, finds all possible original characters using `valueToKeysMap`, and recursively calls itself for each possibility.
  - The base case for the recursion is when the end of `word2` is reached. At this point, the fully decrypted string is checked against the dictionary `HashSet`. If it exists, a counter is incremented.

## Pre-computation of Encrypted Dictionary
This approach optimizes the decryption process by performing heavy computations upfront in the constructor. Instead of decrypting `word2` and checking against the dictionary, we encrypt every word in the dictionary and store the results. This makes the `decrypt` operation a simple and fast lookup.
**Time:** Constructor: `O(K + D * L_d)`. `encrypt`: `O(L_w1)`. `decrypt`: `O(L_w2)`. The constructor pre-encrypts all dictionary words. Decryption is a fast hash map lookup. · **Space:** O(K + D * L_d). `O(K)` for the encryption map and `O(D * L_d)` for the encrypted dictionary map, where D is dictionary size and L_d is average word length.
**Pros:** Extremely fast `decrypt` operation (O(L_w2)), making it suitable for frequent calls.; The one-time pre-computation cost in the constructor is acceptable given the problem constraints.
**Cons:** Higher memory usage due to storing all encrypted dictionary words and their counts.; The constructor does more work, leading to a slightly longer initialization time.
### Explanation
The key idea of this optimized approach is to shift the computational burden from the `decrypt` method to the constructor. Since `decrypt` may be called many times, we pre-process the entire dictionary once. During initialization, we iterate through every word in the `dictionary`, encrypt it, and store the result in a hash map (`encryptedDictionaryCounts`). This map's keys are the encrypted strings, and its values are the number of dictionary words that produce that encrypted string. Consequently, the `decrypt(word2)` method reduces to a single, efficient lookup in this pre-computed map. The `encrypt` method's implementation remains a simple and fast character-by-character mapping.

```java
class Encrypter {
    private Map<Character, String> keyToValueMap = new HashMap<>();
    private Map<String, Integer> encryptedDictionaryCounts = new HashMap<>();

    public Encrypter(char[] keys, String[] values, String[] dictionary) {
        for (int i = 0; i < keys.length; i++) {
            keyToValueMap.put(keys[i], values[i]);
        }

        for (String word : dictionary) {
            String encryptedWord = encryptWord(word);
            if (encryptedWord != null) {
                encryptedDictionaryCounts.put(encryptedWord, encryptedDictionaryCounts.getOrDefault(encryptedWord, 0) + 1);
            }
        }
    }

    // Helper for constructor and public API
    private String encryptWord(String word) {
        StringBuilder sb = new StringBuilder();
        for (char c : word.toCharArray()) {
            String val = keyToValueMap.get(c);
            if (val == null) {
                return null; // Character not in keys, cannot be encrypted
            }
            sb.append(val);
        }
        return sb.toString();
    }

    public String encrypt(String word1) {
        // The problem guarantees all chars in word1 are in keys.
        return encryptWord(word1);
    }

    public int decrypt(String word2) {
        return encryptedDictionaryCounts.getOrDefault(word2, 0);
    }
}
```
### Algorithm
- **Initialization (`Encrypter` constructor):**
  - Build a `HashMap<Character, String>` (`keyToValueMap`) for encryption.
  - Initialize a `HashMap<String, Integer>` (`encryptedDictionaryCounts`).
  - For each `word` in the `dictionary`:
    - Encrypt the `word` using `keyToValueMap`.
    - If the encryption is possible, put the `encryptedWord` into `encryptedDictionaryCounts` and increment its count.
- **Encryption (`encrypt` method):**
  - Same as the previous approach, use `keyToValueMap` to build the encrypted string by iterating through `word1`.
- **Decryption (`decrypt` method):**
  - Simply look up `word2` in the pre-computed `encryptedDictionaryCounts` map.
  - Return the count found, or 0 if it's not in the map.

# Solutions
### Java

```java
class Encrypter { private Map < Character , String > mp = new HashMap <>(); private Map < String , Integer > cnt = new HashMap <>(); public Encrypter ( char [] keys , String [] values , String [] dictionary ) { for ( int i = 0 ; i < keys . length ; ++ i ) { mp . put ( keys [ i ], values [ i ]); } for ( String w : dictionary ) { w = encrypt ( w ); cnt . put ( w , cnt . getOrDefault ( w , 0 ) + 1 ); } } public String encrypt ( String word1 ) { StringBuilder sb = new StringBuilder (); for ( char c : word1 . toCharArray ()) { if (! mp . containsKey ( c )) { return "" ; } sb . append ( mp . get ( c )); } return sb . toString (); } public int decrypt ( String word2 ) { return cnt . getOrDefault ( word2 , 0 ); } } /** * Your Encrypter object will be instantiated and called as such: * Encrypter obj = new Encrypter(keys, values, dictionary); * String param_1 = obj.encrypt(word1); * int param_2 = obj.decrypt(word2); */
```

### CPP

```cpp
class Encrypter { public: unordered_map < string , int > cnt ; unordered_map < char , string > mp ; Encrypter ( vector < char >& keys , vector < string >& values , vector < string >& dictionary ) { for ( int i = 0 ; i < keys . size (); ++ i ) mp [ keys [ i ]] = values [ i ]; for ( auto v : dictionary ) cnt [ encrypt ( v )] ++ ; } string encrypt ( string word1 ) { string res = "" ; for ( char c : word1 ) { if ( ! mp . count ( c )) return "" ; res += mp [ c ]; } return res ; } int decrypt ( string word2 ) { return cnt [ word2 ]; } }; /** * Your Encrypter object will be instantiated and called as such: * Encrypter* obj = new Encrypter(keys, values, dictionary); * string param_1 = obj->encrypt(word1); * int param_2 = obj->decrypt(word2); */
```

### Python

```python
class Encrypter : def __init__ ( self , keys : List [ str ], values : List [ str ], dictionary : List [ str ]): self . mp = dict ( zip ( keys , values )) self . cnt = Counter ( self . encrypt ( v ) for v in dictionary ) def encrypt ( self , word1 : str ) -> str : res = [] for c in word1 : if c not in self . mp : return '' res . append ( self . mp [ c ]) return '' . join ( res ) def decrypt ( self , word2 : str ) -> int : return self . cnt [ word2 ] # Your Encrypter object will be instantiated and called as such: # obj = Encrypter(keys, values, dictionary) # param_1 = obj.encrypt(word1) # param_2 = obj.decrypt(word2)
```