Encrypt and Decrypt Strings

#1579 Most AskedHard

Encrypt and Decrypt Strings #1579 Most Asked

Hard

10 views

Topics:

StringsArrays

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What characters can the input string contain (e.g., only ASCII, Unicode, alphanumeric, special characters)?
What is the expected length range of the input string, and what is the maximum allowed key size?
Should I handle empty strings or null inputs, and if so, how?
What encryption/decryption method should I use, or am I free to choose one myself?
If the input string cannot be encrypted/decrypted using the key (e.g., key is invalid, or operation is impossible), what should the function return?

Brute Force Solution

Approach

The brute force approach to encrypting and decrypting strings involves trying every possible key until the correct one is found. It's like trying every combination on a lock until it opens. This is generally not a good idea because it takes a very long time.

Here's how the algorithm would work step-by-step:

Start by guessing a possible encryption key.
Use this key to try to decrypt the encrypted text.
Compare the result of the decryption to the original text.
If they match, you found the correct key, and you're done.
If they don't match, try a different key.
Repeat this process of guessing, decrypting, and comparing until you find the key that works, or you've tried every possible key.

Code Implementation

def brute_force_decrypt(encrypted_text, original_text): 
    for possible_key in range(256): 
        decrypted_text = ""

        for character in encrypted_text:
            decrypted_character = chr(ord(character) ^ possible_key)
            decrypted_text += decrypted_character

        # Check if decrypted text matches the original text

        if decrypted_text == original_text:

            return possible_key

    return None

def brute_force_encrypt(original_text, encryption_key):
    encrypted_text = ""
    for character in original_text:
        encrypted_character = chr(ord(character) ^ encryption_key)
        encrypted_text += encrypted_character
    return encrypted_text

def encrypt_and_decrypt(original_text):
    encryption_key = 42
    encrypted_text = brute_force_encrypt(original_text, encryption_key)

    # Attempt to find the original key via decryption
    found_key = brute_force_decrypt(encrypted_text, original_text)

    # If the key is found, return
    if found_key is not None:

        return encrypted_text, found_key
    else:
        return None, None

Big(O) Analysis

Time Complexity

O(k*d) – The brute force approach iterates through all possible keys. Let k represent the total number of possible keys. For each key, we perform a decryption operation. Let d represent the time complexity of the decryption operation. The algorithm will try each of the k keys and perform the decryption function that takes d time, in the worst-case scenario. Therefore, the overall time complexity is O(k*d).

Space Complexity

O(1) – The described brute-force approach primarily involves iterative decryption attempts using different keys. It doesn't explicitly state the creation of any auxiliary data structures to store intermediate results or track visited keys. The process mainly compares the decrypted string with the original, potentially storing a temporary decrypted string for comparison, but the size of this string would be bound by the input size but its reuse means no additional space relative to the input size N is required. Therefore, the auxiliary space used remains constant, independent of the input string's length.

Optimal Solution

Approach

To encrypt and decrypt strings efficiently, we'll use a simple substitution method based on a key. Encryption transforms the original message, while decryption reverses it using the same key.

Here's how the algorithm would work step-by-step:

First, agree on a secret key between the sender and receiver. This key determines how the characters in the message will be changed.
For encryption, take each character in the original message and find its corresponding substitute character based on the key.
Replace each character with its substitute to create the encrypted message.
For decryption, take the encrypted message and again use the secret key, but this time to find the original characters.
Replace each encrypted character with its original counterpart to recover the original message.
If a character isn't in the key, you could leave it as is or have a default substitution. It's important to document the process.
This approach ensures that only someone with the secret key can turn the encrypted message back into the original message.

Code Implementation

def encrypt_string(plain_text, encryption_key):
    encrypted_text = ''
    for character in plain_text:
        if character in encryption_key:
            encrypted_text += encryption_key[character]
        else:
            encrypted_text += character

    return encrypted_text

def decrypt_string(encrypted_text, encryption_key):
    # Need to reverse the key for decryption
    decryption_key = {value: key for key, value in encryption_key.items()}

    decrypted_text = ''
    for character in encrypted_text:
        # Attempt decryption, leave character untouched if not in key.
        if character in decryption_key:
            decrypted_text += decryption_key[character]

        else:
            decrypted_text += character

    return decrypted_text

Big(O) Analysis

Time Complexity

O(n) – The encryption and decryption processes each iterate through the input string once. For each character in the string of length n, we perform a constant-time lookup in the key (hash map or similar). Therefore, the time complexity for both encryption and decryption is directly proportional to the length of the input string. Consequently, the overall time complexity is O(n).

Space Complexity

O(K) – The space complexity depends on the size of the key, which determines the substitution mapping. We need to store this key in some form, likely a dictionary or hash map, to enable efficient lookups for encryption and decryption. If the key contains mappings for K characters, storing this mapping requires space proportional to K. Thus, the auxiliary space used is O(K), where K is the number of characters in the key.

Edge Cases

Case	How to Handle
Null or empty input string for encryption	Return an empty string or throw an IllegalArgumentException, depending on requirements.
Null or empty key for encryption/decryption	Throw an IllegalArgumentException to indicate an invalid state.
Key length is zero	Treat this as no encryption, return the original string or throw an exception.
Very long input string (performance implications)	Ensure that the algorithm scales linearly or better with string length to avoid timeouts.
Key contains special characters or non-ASCII characters	Define and document the supported character set for the key and input, handling unsupported characters appropriately (e.g., by excluding them or throwing an exception).
Input string contains non-alphanumeric characters when the algorithm is expecting only alphanumeric input.	Handle non-alphanumeric characters either by removing them, encoding them differently, or throwing an error.
Encryption results in non-printable characters	Use Base64 encoding or another suitable encoding scheme to represent the encrypted string as printable characters.
Decryption key is incorrect/corrupted	Return an error indicating an invalid key or potentially return a garbled/incorrectly decrypted string (depending on requirements).

Null or empty input string for encryption

How to Handle:

Return an empty string or throw an IllegalArgumentException, depending on requirements.

Null or empty key for encryption/decryption

How to Handle:

Throw an IllegalArgumentException to indicate an invalid state.

Key length is zero

How to Handle:

Treat this as no encryption, return the original string or throw an exception.

Very long input string (performance implications)

How to Handle:

Ensure that the algorithm scales linearly or better with string length to avoid timeouts.

Key contains special characters or non-ASCII characters

How to Handle:

Define and document the supported character set for the key and input, handling unsupported characters appropriately (e.g., by excluding them or throwing an exception).

Input string contains non-alphanumeric characters when the algorithm is expecting only alphanumeric input.

How to Handle:

Handle non-alphanumeric characters either by removing them, encoding them differently, or throwing an error.

Encryption results in non-printable characters

How to Handle:

Use Base64 encoding or another suitable encoding scheme to represent the encrypted string as printable characters.

Decryption key is incorrect/corrupted

How to Handle:

Return an error indicating an invalid key or potentially return a garbled/incorrectly decrypted string (depending on requirements).