Coding interview Essentials

12. String Reverse

String Reverse

Introduction

Reversing a collection of items or a string is a ubiquitous operation, and because of that it is very often asked during programming interviews. Due to its simplicity, it is often part of a set of warm-up problems in the interviewer’s question list.

There are really only two variations of this problem:

  1. in-place where we are asked explicitly not to use any additional space and to modify the input string;

  2. out-of-place, where we are free to return a brand new collection.

If the statement is not clear on this point, then it is important to first clarify which type the interviewer is intending.

Let’s first consider how popular and difficult this problem is: it is important to focus on getting the solution right at the first try and in a relatively short time frame; in addiction, we have to make sure the communication is clear, concise, and precise and that we engage the interviewer into following our reasoning process. The interviewer is expecting us to have seen (or solved) this question more than once in the past: therefore, more than on the algorithm itself, in order to be able to stand out among all the other candidates, our communication and implementation should be spot-on.

Problem statement

Write a function that takes a string \(s\) of length \(n\) and reverses it.


Given \(s="abcde"\) the function produces \(s="edcba"\).


Given \(s="programming"\) the function produces \(s="gnimmargorp"\).

Clarification Questions

Should the function reverse the string in place?

Yes, a copy of the input cannot be created.

Is the empty string a valid input?

Yes, the input string might be empty.

Discussion

We have to reverse a string in place. But what does it exactly mean to do it in-place? What it means is that no auxiliary storage is allowed, that the input itself will be processed and modified by the function, and that it will be eventually transformed into the output. Since the original content of the input is lost once the function is terminated, in-place algorithms are also called destructive. However, having to use no additional storage space does not literally mean that not even a single additional byte of space can be utilized. This constraint should be interpreted more like as a copy of the input is disallowed, or as the function should work in \(O(1)\) (constant) space.

In order to develop an intuitive idea of how we can solve this problem, it is useful to take a deeper look at what happens to each letter of \(s\) once is reversed. For instance, consider the string \(s=a_0 a_1 a_2 a_3 a_4 a_5\) which is transformed into \(s'=a_5 a_4 a_3 a_2 a_1 a_0\). The subscript \(i\) in \(a_i\) identifies the position in which the letter \(a_i\) appears in the original input string \(s\). The core of the problem is to figure out how the letters are shuffled around from their original position to their final location in the reversed string. In order to do so, let’s have a look at how the indices are moved during the reverse process by comparing the positions of a letter in the original and in the reversed string.

Table 13.1 shows how indices of string \(s=a_0 a_1 a_2 a_3 a_4 a_5\) are shuffled around and contains all the information that is necessary to deduce the function that maps the indices of the original string into the indices of the reversed string. An index \(i\) gets mapped to an index \(j\) s.t. \(i+j = n\) (index \(2\) goes to \(3\) and \(2+3=5\) for instance). A quick manipulation of that equation shows that \(j\) (the index in the reversed string where the letter at index \(i\) in the original string is mapped to) is equal to: \(j = n-i\). We know now which elements to swap in order to obtain a reversed list. This information can be used to reverse the entire string as shown in Listing [list:string_reverse_1].

Indices shuffling for the reversal of \(s=a_0 a_1 a_2 a_3 a_4 a_5\).
Index in Input Index in Output
0 5
5 0
1 4
4 1
3 2
2 3

Listing 1: Linear time constant space iterative solution.

void reverse_string_inplace(std::string &s)
{
  const int len = s.length();
  for (int i = 0; i < len / 2; i++)
    swap(s[i], s[len - 1 - i]);
}

An important detail we can notice in Listing [list:string_reverse_1] is how the loop terminates only after \(\frac{n}{2}\) iterations. This is necessary because a swap operation on the index \(i<\frac{n}{2}\) involves two elements: the element at index \(i\), but also its symmetrical sibling at index \(n-i\) in the second half of the string. If the loop would not terminate at \(\frac{n}{2}\), then each element \(a_i\) would be involved in two swap operations. For instance, for the letter at index \(0\), the following swaps would occur:

Clearly, applying two (or any even number) swap operations on the same indices is equivalent to a no-op, and it results in having the letters involved in the swaps stay at their original locations. Therefore, if the loop does not terminate after \(\frac{n}{2}\) iterations, then the function would not modify the original string at all!

This solution is considered good because, besides being short and expressive, it has a time and space complexity of \(O(n)\) and \(O(1)\), respectively, which are optimal.

Common Variation

Out-of-place solution

Sometimes the interviewer might ask for an easier version of this problem, where the memory constraint is relaxed and we are allowed to allocate linear space. This version is easier compared to the in-place version: we can simply construct the reversed string by looping the original string backward, as shown in Listing [list:string_reverse_outplace_rawloop] and Listing [list:string_reverse_outplace_iterators]

Listing 2: Linear time and space iterative out-of-place solution using raw loops.

std::string reverse_string_outplace_raw_loop(const std::string &s)
{
  std::string ans;
  ans.reserve(s.size());

  for (int i = s.size() - 1; i >= 0; i--)
    ans.push_back(s[i]);

  return ans;
}

Listing 3: Linear time and space iterative iterative out-of-place solution using iterators.

std::string reverse_string_outplace_iterator(const std::string &s)
{
  std::string ans;
  ans.reserve(s.size());

  auto it_s = std::prev(end(s));
  while (it_s >= s.begin())
  {
    ans.push_back(*it_s);
    --it_s;
  }

  return ans;
}

Recursive solution

The interviewer might as well explicitly ask for a recursive implementation. This problem is well suited for recursion; in fact, a look at the iterative linear time and constant space solution above shows that at any given point in the loop, the status of the string is the following: \(a_{n-1}a_{n-2} \ldots a_k a_{k+1} \ldots a_l a_{k-1}a_{k-2} \ldots a_0\). There is always a portion of the string delimited by two indices \(k\) and \(l\), \(k \leq l\), which is yet to be processed (i.e. with the letters un-swapped). This fact can be used to write a recursive solution; At first \(k=0\) and \(l=n-1\) and the string can be reversed by swapping \(a_k=0\) and \(a_l=n-1\) and by recursively reversing the inner part of the string i.e. in the range \(k=1\) and \(l=n-2\). The inner part can be reversed using the same logic, and this reasoning can be applied for all the recursive calls right until \(k \geq l\). At that point, the function can simply terminate and the input string is reversed successfully. Equation [eq:string_reversal_recursion] formalizes this idea and a possible implementation is shown in Listing [list:string_reversal_recursion].

\[R(s, k, l)= \begin{cases} \text{swap}(s[k]s[l]) \: \wedge \: R(s,k+1, l-1) & \text{if } k\geq l\\ \text{return} & \text{otherwise} \end{cases} \label{eq:string_reversal_recursion}\]

Listing 4: Recursive in-place solution.

void reverse_string_inplace_recursive_helper(std::string &s,
                                             const int k,
                                             const int l)
{
  if (k >= l)
    return;

  swap(s[k], s[l]);
  reverse_string_inplace_recursive_helper(s, k + 1, l - 1);
}

void reverse_string_inplace_recursive(std::string &s)
{
  reverse_string_inplace_recursive_helper(s, 0, s.size() - 1);
}

The complexity analysis for this approach can be a bit controversial, especially the one concerning space because we have to consider also the stack space utilized by all the recursive calls, which can theoretically amount to \(O(n)\). However, a compiler optimizer worth that title would optimize it so as to use constant space. It is therefore important to clarify this aspect with the interviewer.

Discussing this topic might open the possibility for questions related to recursion, and especially regarding the Tail Call Optimization (TCO)[^10], so one needs to be careful while opening this pandora box.

The time complexity is linear.