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 initiallyempty 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 leftmost of the two central characters) Append the encrypted version of the substring of S that’s to the left of the middle character (if nonempty) Append the encrypted version of the substring of S that’s to the right of the middle character (if nonempty) 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 lowercase 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
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.
Initial Breakdown:
 Find the middle character of the string.
 Encrypt the left and right substrings.
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.
Task Identification:
 Finding the middle character.
 Recursively encrypting the left substring.
 Recursively encrypting the right substring.
Task Abstraction:
 Each of these tasks is selfcontained and reusable.
Method Naming:
find_middle_character
,encrypt_substring
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:


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.