Encrypted Words

Facebook recruiting portal.

You’ve devised a simple encryption method for alphabetic strings that shuffles the characters in such a way that the resulting string is hard to quickly read, but is easy to convert back into the original string.

When you encrypt a string S, you start with an initially-empty resulting string R and append characters to it as follows:

Append the middle character of S (if S has even length, then we define the middle character as the left-most of the two central characters) Append the encrypted version of the substring of S that’s to the left of the middle character (if non-empty) Append the encrypted version of the substring of S that’s to the right of the middle character (if non-empty) For example, to encrypt the string “abc”, we first take “b”, and then append the encrypted version of “a” (which is just “a”) and the encrypted version of “c” (which is just “c”) to get “bac”. If we encrypt “abcxcba” we’ll get “xbacbca”. That is, we take “x” and then append the encrypted version “abc” and then append the encrypted version of “cba”.

Input S contains only lower-case alphabetic characters 1 <= |S| <= 10,000

Output Return string R, the encrypted version of S.

Example 1 S = “abc” R = “bac”

Example 2 S = “abcd” R = “bacd”

Example 3 S = “abcxcba” R = “xbacbca”

Example 4 S = “facebook” R = “eafcobok”

My Solution T = O(n) where n is number of calls S = O(logn) where n is number of stacks but length of string is cut in half each time

1. Problem Understanding:

   • Encrypt a given string by recursively appending its middle character, the encrypted version of its left substring, and the encrypted version of its right substring.

2. Initial Breakdown:

   • Find the middle character of the string.
   • Encrypt the left and right substrings.

3. Subproblem Refinement:

   • Find the middle character: We need the index for that.
   • Encrypt the left substring: Call the same encryption function recursively.
   • Encrypt the right substring: Again, call the same function recursively.

4. Task Identification:

   • Finding the middle character.
   • Recursively encrypting the left substring.
   • Recursively encrypting the right substring.

5. Task Abstraction:

   • Each of these tasks is self-contained and reusable.

6. Method Naming:

   • find_middle_character, encrypt_substring

7. Subproblem Interactions:

   • Finding the middle character is done before encrypting the substrings. The encrypted left and right substrings are then appended in order.

Here is Python code for the solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

def encrypt_string(s):
    # Base case: If the string is empty or has only one character
    if not s:
        return ""
    if len(s) == 1:
        return s

    n = len(s)
    mid_idx = n // 2

    # For even-length strings, choose the left-most of the two middle characters
    if n % 2 == 0:
        mid_idx -= 1

    mid_char = s[mid_idx]

    # Recursive calls for the left and right substrings
    left_encrypted = encrypt_string(s[:mid_idx])
    right_encrypted = encrypt_string(s[mid_idx+1:])

    return mid_char + left_encrypted + right_encrypted

# Test cases
print(encrypt_string("abc"))  # Output should be "bac"
print(encrypt_string("abcd"))  # Output should be "bacd"
print(encrypt_string("abcxcba"))  # Output should be "xbacbca"
print(encrypt_string("facebook"))  # Output should be "eafcobok"

Time Complexity: O(n)
Each recursive call processes each character of the string exactly once.

Space Complexity: O(log n)
Since the string is divided by 2 at each recursive call, the maximum depth of the recursion stack is log n.