Encrypt and Decrypt Strings - Practice Coding Problems

Encrypt and Decrypt Strings - 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.

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

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

Input & Output

Example 1 — Basic Encryption/Decryption

$ Input: keys = ['a', 'b', 'c'], values = ["hj", "xy", "wz"], dictionary = ["ab", "bc"], operations = [["encrypt", "ab"], ["decrypt", "hjxy"]]

› Output: ["hjxy", "1"]

💡 Note: Encrypt 'ab': 'a'→"hj", 'b'→"xy", result "hjxy". Decrypt "hjxy": splits to "hj"+"xy" which could be 'a'+'b'="ab", and "ab" exists in dictionary, so count is 1.

Example 2 — Multiple Dictionary Matches

$ Input: keys = ['a', 'b'], values = ["hj", "hj"], dictionary = ["aa", "bb"], operations = [["decrypt", "hjhj"]]

› Output: ["2"]

💡 Note: Decrypt "hjhj": both 'a' and 'b' map to "hj", so "hjhj" could decode to "aa" or "bb". Both exist in dictionary, so count is 2.

Example 3 — Invalid Encryption

$ Input: keys = ['a', 'b'], values = ["hj", "xy"], dictionary = ["ab"], operations = [["encrypt", "ac"]]

› Output: [""]

💡 Note: Encrypt 'ac': 'a'→"hj" but 'c' is not in keys array, so encryption fails and returns empty string.

Constraints

1 ≤ keys.length == values.length ≤ 26
values[i].length == 2
1 ≤ dictionary.length ≤ 100
1 ≤ dictionary[i].length ≤ 100
At most 200 calls will be made to encrypt and decrypt

Visualization

Tap to expand

Understanding the Visualization

Input

Keys ['a','b','c'], Values ["hj","xy","wz"], Dictionary ["ab","bc"]

Process

Build char↔code mappings and handle encrypt/decrypt operations

Output

Return encrypted strings or count of valid dictionary matches

Key Takeaway

🎯 Key Insight: Pre-encrypt all dictionary words to transform expensive decryption into O(1) lookup

Asked in

G Google 35 a Amazon 28 M Microsoft 22

The key insight is to pre-encrypt all dictionary words during initialization for O(1) decryption lookup. Best approach uses pre-encrypted frequency map to avoid exponential decoding generation. Time: O(d×m) init + O(n) encrypt + O(1) decrypt, Space: O(d×m)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Decryption	O(n) for encrypt, O(d × 2^k) for decrypt where d is dictionary size, k is ambiguous mappings	O(k + v + d)	Build basic hash maps and count decryptions by checking each dictionary word
Pre-encrypted Dictionary	O(d×m) initialization, O(n) encrypt, O(1) decrypt where d is dictionary size, m is average word length	O(d×m)	Pre-encrypt all dictionary words for instant lookup during decryption

Brute Force Decryption — Algorithm Steps

Step 1: Build hash maps for char→value and value→chars mappings
Step 2: For encryption, replace each character using the map
Step 3: For decryption, generate all possible decodings and count dictionary matches

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Maps

Create char→value and value→chars mappings

Generate Decodings

For encrypted input, try all possible character combinations

Count Matches

Check which generated words exist in dictionary

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Basic implementation placeholder
typedef struct {
    char keys[26];
    char values[26][3];
    char dictionary[1000][20];
    int keyCount;
    int dictCount;
} Encrypter;

char* encrypt(Encrypter* enc, char* word) {
    static char result[1000];
    result[0] = '\0';
    
    for (int i = 0; word[i]; i++) {
        int found = 0;
        for (int j = 0; j < enc->keyCount; j++) {
            if (enc->keys[j] == word[i]) {
                strcat(result, enc->values[j]);
                found = 1;
                break;
            }
        }
        if (!found) {
            result[0] = '\0';
            return result;
        }
    }
    
    return result;
}

int decrypt(Encrypter* enc, char* word) {
    // Simplified implementation
    return 0;
}

char** solution(char* keys[], char* values[], char* dictionary[], char* operations[][2], int opCount) {
    // Implementation placeholder
    static char* results[100];
    return results;
}

int main() {
    // Parse inputs and call solution
    printf("[]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n) for encrypt, O(d × 2^k) for decrypt where d is dictionary size, k is ambiguous mappings

Encryption is linear in word length. Decryption checks all dictionary words against exponentially many possible decodings

✓ Linear Growth

Space Complexity

O(k + v + d)

Hash maps store keys/values mappings plus dictionary

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Decryption — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler