• Difficulty: Easy
• Patterns:
  • Stack

---

Problem Definition

A string s was encrypted with the following algorithm: Create an empty string r.

1. Append the middle character of s to r. If the string has even length, take the character to the left of the middle.
2. Append the encrypted version of the string prior to the middle character.
3. Append the encrypted version of the string after the middle character.

Write a function to decrypt such an encrypted string.

---

Examples

Some test cases to verify our solution.

assert decrypt("bac") == "abc"
assert decrypt("bacd") == "abcd"
assert decrypt("xbacbca") == "abcxcba"

---

Recursive Solution

We'll use recursion to decrypt the string.

def decrypt(s):
    if len(s) < 2:
        return s
    split = len(s) // 2
    if len(s) % 2 == 1:
        split += 1
    return decrypt(s[1:split]) + s[0] + decrypt(s[split:])

assert decrypt("bac") == "abc"
assert decrypt("bacd") == "abcd"
assert decrypt("xbacbca") == "abcxcba"

---

Recursive Solution Complexity

Let $n = $ len(s).

Runtime complexity should be $\Theta(n)$ since we will create $\approx n$ stack frames. Looked at another way, we are creating 2 branches in every call and doing $log(n)$ calls. Therefore we have a runtime of:

$$ \Theta(2^{log(n)}) = \Theta(n) $$

Auxiliary space complexity should be $\Theta(n \cdot log(n))$ since we are creating $\approx log(n)$ stack frames and in each stack frame creating a copy of each half of the string, resulting in an auxiliary space complexity of:

$$ \begin{equation} \begin{split} \Theta \bigg(\sum_{i=1}^{log(n)}{\big (1 + 2 \cdot \frac{n}{2^i}\big )} \bigg) &= \Theta \bigg(log(n) + \sum_{i=1}^{log(n)}{\frac{n}{2^{i-1}}} \bigg) \\ &= \Theta \bigg(log(n) + \sum_{i=1}^{log(n)}{\frac{n}{2^{i-1}}} \bigg) \\ &= \Theta(log(n) + n \cdot log(n)) \\ &= \Theta(n \cdot log(n)) \end{split} \end{equation} $$

---

Stack-Based Solution

We can replace the program stack with our own manually-maintained stack.

Coming soon...