Encrypt and Decrypt Strings

Encrypt and Decrypt Strings

What is this problem about?

The Encrypt and Decrypt Strings coding problem involves designing a system that can transform strings based on a provided mapping.

1. Encryption: Replace each character in a string with a 2-character string based on a keys and values array.
2. Decryption: Given an encrypted string, find how many strings from a provided dictionary would result in that exact encrypted string when encrypted. You need to implement the encrypt and decrypt functions efficiently.

Why is this asked in interviews?

Companies like Amazon and Google use this problem to test a candidate's ability to optimize lookup operations. While encryption is a direct mapping (O(N)), decryption is more complex because many different strings might encrypt to the same result. The Hash Table interview pattern or a Trie interview pattern is usually needed to precompute dictionary encryptions and answer decryption queries in constant time.

Algorithmic pattern used

This is a Design and Precomputation problem.

1. Encryption: Use a Hash Map or array to store char -> 2-char string. This makes encrypt O(Length of string).
2. Decryption (The Trick): Instead of trying to "reverse" the encryption, encrypt every word in the provided dictionary during initialization.
3. Store the counts of these encrypted dictionary words in a Frequency Map (encrypted_string -> count).
4. To decrypt, simply look up the encrypted string in the frequency map and return the count.

Example explanation

Keys: ['a', 'b'], Values: ["11", "22"]. Dictionary: ["aa", "ab"].

1. Encryption of "aa": 'a' -> "11", 'a' -> "11". Result: "1111".
2. Encryption of "ab": 'a' -> "11", 'b' -> "22". Result: "1122".
3. Initialization Map: {"1111": 1, "1122": 1}.
4. decrypt("1111") returns 1.
5. decrypt("1122") returns 1.
6. decrypt("3333") returns 0.

Common mistakes candidates make

• Deciphering character by character: Trying to split the encrypted string into 2-char blocks and finding all possible original characters. This leads to a massive branching factor and exponential time.
• Ignoring the Dictionary: Forgetting that decryption is restricted only to words that exist in the provided dictionary.
• Initialization overhead: Not realizing that pre-encrypting the dictionary is the only way to make the decrypt function fast enough for multiple calls.

Interview preparation tip

In "Design" problems, if one function (decrypt) seems very hard or slow, look for ways to move the work into the constructor or the other function (encrypt). This "heavy initialization, light query" trade-off is a common design pattern.