Problem

An infamous gang of cyber criminals named “The Gray Cyber Mob”, which is behind many hacking attacks and drug trafficking, has recently become a target for the FBI. After intercepting some of their messages, which looked like complete nonsense, the agency learned that they indeed encrypt their messages, and studied their method of encryption.

Their messages consist of lowercase latin letters only, and every word is encrypted separately as follows:

Convert every letter to its ASCII value. Add 1 to the first letter, and then for every letter from the second one to the last one, add the value of the previous letter. Subtract 26 from every letter until it is in the range of lowercase letters a-z in ASCII. Convert the values back to letters.

The FBI needs an efficient method to decrypt messages. Write a function named decrypt(word) that receives a string that consists of small latin letters only, and returns the decrypted word.

Explain your solution and analyze its time and space complexities.

Since the function should be used on messages with many words, make sure the function is as efficient as possible in both time and space. Explain the correctness of your function, and analyze its asymptotic runtime and space complexity.

Note: Most programing languages have built-in methods of converting letters to ASCII values and vice versa. You may search the internet for the appropriate method.

Examples

Example 1

1
2
3
4
5
6
7
8

input:  word = "dnotq"
output: "crime"
Explanation:
Decrypted message: c r i m e
Step 1: 99 114 105 109 101
Step 2: 100 214 319 428 529
Step 3: 100 110 111 116 113
Encrypted message: d n o t q

Example 2

1
2

input:  word = "flgxswdliefy"
output: "encyclopedia"

Constraints

  • [time limit] 5000ms
  • [input] string word
    • The ASCII value of every char is in the range of lowercase letters a-z.
  • [output] string

Solution

Method 1 – Reverse Cumulative ASCII Shift

Intuition

The encryption process shifts each character’s ASCII value by the sum of all previous encrypted values, wrapping around if it goes below ‘a’. To decrypt, we reverse this process: for each character, subtract the cumulative sum so far, and if the result is below ‘a’, wrap it back into the lowercase range. This reconstructs the original word.

Approach

  1. Initialize a variable to track the cumulative sum (start with 1 for the first character).
  2. For each character in the encrypted word:
    • Convert it to its ASCII value.
    • Subtract the cumulative sum from this value.
    • If the result is less than ‘a’, add 26 until it is in the lowercase range.
    • Convert the result back to a character and append to the answer.
    • Update the cumulative sum by adding the decrypted character’s ASCII value.
  3. Return the constructed answer string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
	string decrypt(string word) {
		string ans = "";
		int sumSoFar = 1;
		for (char ch : word) {
			int charCode = ch - sumSoFar;
			while (charCode < 'a') charCode += 26;
			ans += (char)charCode;
			sumSoFar += charCode;
		}
		return ans;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func decrypt(word string) string {
	ans := ""
	sumSoFar := 1
	for i := 0; i < len(word); i++ {
		charCode := int(word[i]) - sumSoFar
		for charCode < int('a') { charCode += 26 }
		ans += string(byte(charCode))
		sumSoFar += charCode
	}
	return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
	public String decrypt(String word) {
		StringBuilder ans = new StringBuilder();
		int sumSoFar = 1;
		for (char ch : word.toCharArray()) {
			int charCode = ch - sumSoFar;
			while (charCode < 'a') charCode += 26;
			ans.append((char)charCode);
			sumSoFar += charCode;
		}
		return ans.toString();
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
	fun decrypt(word: String): String {
		val ans = StringBuilder()
		var sumSoFar = 1
		for (ch in word) {
			var charCode = ch.code - sumSoFar
			while (charCode < 'a'.code) charCode += 26
			ans.append(charCode.toChar())
			sumSoFar += charCode
		}
		return ans.toString()
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
	def decrypt(self, word: str) -> str:
		ans = []
		sum_so_far = 1
		for ch in word:
			char_code = ord(ch) - sum_so_far
			while char_code < ord('a'):
				char_code += 26
			ans.append(chr(char_code))
			sum_so_far += char_code
		return ''.join(ans)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
	pub fn decrypt(word: String) -> String {
		let mut ans = String::new();
		let mut sum_so_far = 1;
		for ch in word.bytes() {
			let mut char_code = ch as i32 - sum_so_far;
			while char_code < b'a' as i32 { char_code += 26; }
			ans.push(char_code as u8 as char);
			sum_so_far += char_code;
		}
		ans
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
	decrypt(word: string): string {
		let ans = '';
		let sumSoFar = 1;
		for (const ch of word) {
			let charCode = ch.charCodeAt(0) - sumSoFar;
			while (charCode < 97) charCode += 26;
			ans += String.fromCharCode(charCode);
			sumSoFar += charCode;
		}
		return ans;
	}
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the word, since we process each character once.
  • 🧺 Space complexity: O(n), for the output string of length n.