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”

Encrypted Words by Recursion

The problem is inherently recursive. The algorithm of Encryption can be implemented straightforward by Recursion. First we need to define the terminal cases when the given string is empty or a single character – which we can just return it.

1
2
3
4
5
6
7

string findEncryptedWord(string s) {
  if (s.empty()) return "";
  if (s.size() == 1) return s;
  int mid = (s.size() & 1) ? s.size() / 2 : (s.size() / 2 - 1);
  return s[mid] + findEncryptedWord(s.substr(0, mid)) + 
                  findEncryptedWord(s.substr(mid + 1));
}

string findEncryptedWord(string s) {
  if (s.empty()) return "";
  if (s.size() == 1) return s;
  int mid = (s.size() & 1) ? s.size() / 2 : (s.size() / 2 - 1);
  return s[mid] + findEncryptedWord(s.substr(0, mid)) + 
                  findEncryptedWord(s.substr(mid + 1));
}

Then, we can divide the string by middle into half – recursively obtaining the encrypted strings of both parts, then concatenate the three parts recursively. The time complexity is O(N) if we consider the string concatenation time is O(1) constant. Otherwise, it will be O(N^2) if the string concatenation complexity is O(N).

The space complexity is O(N) where N is the number of the characters in the given unencrypted string. This is due to the fact that we have to allocate space for the encrypted string, and also the stack usage of the stack due to recursion.

–EOF (The Ultimate Computing & Technology Blog) —