loading...
Cover image for Reversing a String in Place

Reversing a String in Place

alisabaj profile image Alisa Bajramovic ・4 min read

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Today's algorithm of the day is the Reverse String problem:

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. You may assume all the characters consist of printable ascii characters.

This kind of problem (and variations on it) pop up all the time, so knowing how to modify an array in place is a super useful skill.

Today, I'm going to be solving this problem with two pointers--one at each end of the array--and "swapping" the letters at those spots. I'll start by going over the approach I'll be taking, and then I'll code out the solution using JavaScript.

Approaching this Problem

The idea behind a two pointer solution is to have a pointer at each end of a word (or array), to swap the letters at those points, and to keep moving the two pointers toward the middle of the word. By the time the pointers meet in the middle, the word will be reversed.

To better explain this idea, I'll use an example. We'll start with the word "TANDEM", and two pointers. The left pointer is at start, the "T", and the right pointer is at the end, the "M".

Each letter of "TANDEM" in its own block. Blue arrow with the word "left" pointing to the "T", and red arrow with the word "right" pointing to the "M".

Now, we'll want to swap these two letters: "T" will go in the "M" spot, and "M" will go in the "T" spot. After swapping, we get the string "MANDET".

First there is the same word in the blocks from before. A blue arrow from the left letter pointing to the right letter, and a red arrow from right letter pointing to the left letter. Below that is the result of swapping those letters: "MANDET".

Now we can move our pointers toward the center. The left pointer is now on the "A", and the right pointer is on the "E". We will swap these letters, putting the "A" where the "E" was, and the "E" where the "A" was. After swapping, we get "MENDAT".

Blue left arrow pointing to the "A", and red right arrow pointing to the "E". Arrows beneath the word signify "swapping" those letters. Blue curved arrow points from the "A" spot to the "E" spot, and red curved arrow points from the "E" spot to the "A" spot. Below that is the result of this swap: "MENDAT".

Again we move the pointers toward the center. The left pointer is on "N", and the right pointer is on "D". We'll swap these letters, and we have "MEDNAT", which is "TANDEM" backwards.

Blue left arrow points to the "N", and red right arrow points to the "D". Curved arrows beneath the word demonstrate the "swap", with blue arrow pointing from the "N" to the "D", and red arrow pointing from the "D" to the "N". Beneath that is the final result, "MEDNAT", which is the given word, "TANDEM", backwards.

We know to stop because we always want the left pointer to be to the left of the right pointer. In other words, we'll want the process to keep going until the pointers meet at the middle.

Coding the Solution

Now that we've walked through how this solution would work, we can move onto coding it. To start, we'll want to make the pointers, left and right. We'll set left equal to 0, so that it starts at the beginning, and we'll set right equal to the length of the string minus 1, so that it starts at the end of the string (remember that indexing starts at 0).

function reverseString(str) {
  let left = 0;
  let right = str.length - 1;
  //...
}

We'll want to keep doing something until left and right meet at the middle, which means this is a good time to use a while loop. As long as left is less than right (aka to the left of right), we'll want to be swapping the letters.

function reverseString(str) {
  let left = 0;
  let right = str.length - 1;
  while (left < right) {
    //...
  }
}

To do the swapping, we'll need to create two variables, which will both temporarily store the values at each index. We need these temporary variables or else the swapping couldn't work. To see why, let's briefly look at the example of "CAT". If we wanted to reverse this string, and didn't use temporary variables, we'd do something like

//...
str[left] = str[right] // right now, str = "TAT"
str[right] = str[left] // again, str = "TAT"
//...

Without temporary variables, therefore, we wouldn't have a way of "remembering" which variable used to be at the index.

So, we'll create tempStart and tempEnd. tempStart will store the variable at the left index, and tempEnd will store the variable at the right index.

function reverseString(str) {
  let left = 0;
  let right = str.length - 1;
  while (left < right) {
    const tempStart = str[left];
    const tempEnd = str[right];
    //...
  }
}

Now that the values are stored in these temporary variables, we can go ahead and swap them. We'll set the value at the left pointer equal to tempEnd, and the value at the right pointer equal to tempStart. And finally, we'll move the pointers--left will increment, and right will decrement, so that they both go toward the center.

function reverseString(str) {
  let left = 0;
  let right = str.length - 1;
  while (left < right) {
    const tempStart = str[left];
    const tempEnd = str[right];
    str[left] = tempEnd;
    str[right] = tempStart;
    left++;
    right--;
  }
}

This two pointer iterative approach is done in constant space (O(1)) and linear time (O(n)).

As always, let me know in the comments if you have any questions or ideas!

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Posted on by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

markdown guide