python

Reversing a String

2020-07-04
exercises
2 min read

def reverse(s):
  s = [x for x in s]
  l = len(s)
  for i in range(l // 2):
      s[i], s[l-i-1] = s[l-i-1], s[i]
  return ''.join(s)

#Challenge

Source	Language	Runtime
DailyByte	python	$O (n)$

#Solution

for every pair of characters leading to the middle of the string, swap them.

#Proof

Loop Invariant: at the end of each iteration of the loop, the character at index $i$ and the character at index $l - i - 1$ is at its correct position in the reversed string.

Let $m$ be the middle of the string. This is equal to $f l o o r (l e n (s) / 2)$ .

In the first iteration $i = 0$ . The first character ( $0$ ) is moved to the end of the string and the last character ( $l - i - 1$ ) is moved to the start of the string. Maintaining the loop invariant.
In the $k^{t h}$ iteration, for any $k$ less than $m$ , the $k^{t h}$ value is $m - k$ characters from the middle of the string and $2 m - k - 1$ characters from its position in the reversed string. $2 m = l$ . Thus the $k^{t h}$ value is moved to the $l - k - 1$ ^st position and the $l - k - 1$ ^st value is moved to the $k^{t h}$ position. Maintaining the loop invariant.
At the end of the loop there's a case split depending on if the string length is odd or even.
- If the string is odd then $i = m - 1$ . The $m - 1$ ^st and the $m + 1$ ^th characters are swapped. Loop invariant holds and the loop terminates.
- If the string is even then $i = m - 1$ and this character is swapped with $l - (m - 1) - 1$ ^st character which is the character next to $i$ (I.E $i + 1 = m$ ). The last pair of characters is swapped. The loop invariant holds and the loop terminates.

Note

in the case where the string is odd, the mth character isn't moved because it's position is the same in the reversed string as it was in the original.

#Alternative Implementation

Python itself has a simple clean way to reverse collections. Here's the language specific solution.

def reverse(s):
    return s[::-1]