The only way to get better at solving algorithms and data structures is to power through a few.
We covered the best ways to prepare in this lesson, in this one, and here. Be sure to visit those if you need some more guidance. Otherwise, let's jump into it.
Reverse a String
Let's reverse a string!
Can you write a function that reverses an inputted string without using the built-in Array#reverse
method?
Let's look at some examples. So, calling:
reverseString("jake")
should return "ekaj"
.
reverseString("reverseastring")
should return "gnirtsaesrever"
.
This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.
True or False?
In Java, C#, JavaScript, Python and Go, strings are immutable
. This means the string object's state can't be changed after creation.
Solution: True
On Interviewer Mindset
Reversing a string is one of the most common technical interview questions that candidates get. Interviewers love it because it's deceptively simple. After all, as a software engineer, you'd probably call the #reverse
method on your favorite String
class and call it a day!
So don't overlook this one-- it appears a surprising amount as a warm-up or build-up question. Many interviewers will take the approach of using an easy question like this one, and actually judge much more harshly. You'll want to make you sure really nail this.
How We'll Begin Solving
We want the string reversed, which means that we end up with all our letters positioned backwards. If you need a quick review of string
s, check out our lesson on arrays and strings.
We know that string
s can be thought of as character arrays-- that is, each element in the array is a single character. And if we can assume that, then we know the location (array position) of each character, as well as the index when the array
ends.
There's a caveat to thinking of strings as character arrays-- it's not always true. As readers and viewers have pointed out, a string represents text formed from graphemes (the smallest functional unit of a writing system)-- formed by combining character sequences in unicode.
Though strings and arrays contain similar methods like length
, concat
, and character position access-- they are not identical. As an example, arrays are mutable and strings usually are not. Before we can operate on the string as an array, we'll need to separate the units (in JS by calling the .split()
method, or bypass this property by generating a brand new string instead of trying to operate on the original.
However, after the split
operation, we can apply that paradigm to operating on this string. Thus we can step through each of its indices. Stepping through the beginning of the string, we'll make these observations at each point:
const str = "JAKE";
// position 0 - "J"
// position 1 - "A"
// ...
Since a reversed string is just itself backwards, a brute force solution could be to use the indices, and iterate from the back to the front.
See the code attached and try to run it using Run Sample Code
. You'll see that we log out each character from the back of the string!
function reverseString(str) {
let newString = '';
// start from end
for (let i = str.length-1; i >= 0; i--) {
console.log('Processing ', newString, str[i]);
// append it to the string builder
newString = newString + str[i];
}
// return the string
return newString;
}
console.log(reverseString('test'));
Fill In
We want to console.log
out:
5
4
3
2
1
What's the missing line here?
var arr = [1, 2, 3, 4, 5];
for (var i = ___________; i >= 0; i--) {
console.log(arr[i]);
}
Solution: arr.length - 1
Can We Do Better Than Brute Force?
However, it wouldn't really be an interesting algorithms question if there wasn't a better way. Let's see how we can optimize this, or make it run faster. When trying to make something more efficient, it helps to think of things to cut or reduce.
One thing to note is that we're going through the entire string-- do we truly need to iterate through every single letter?
Let's examine a worst case scenario. What if the string is a million characters long? That would be a million operations to work through! Can we improve it?
Yes, With More Pointers!
Well, we're only working with a single pointer right now. The iterator from our loop starts from the back, and appends each character to a new string, one by one. Having gone through The Two Pointer Technique, we may recognize that some dramatic improvements can be had by increasing the number of pointers we use.
By this I mean, we can cut the number of operations in half. How? What if we did some swapping instead? By using a while
loop and two pointers-- one on the left and one on the right.
With this in mind-- the big reveal is that, at each iteration, we can swap the letters at the pointer indices. After swapping, we would increment the left
pointer while decrementing the right
one. That could be hard to visualize, so let's see a basic example listed out.
jake // starting string
eakj // first pass
^ ^
ekaj // second pass
^^
Multiple Choice
What's a good use case for the two pointers technique?
- Shifting indices to be greater at each iteration
- Reducing a solution with a nested for-loop and O(n^2) complexity to O(n)
- Finding pairs and duplicates in a for-loop
- None of these
Solution: Reducing a solution with a nested for-loop and O(n^2) complexity to O(n)
With two pointers, we've cut the number of operations in half. It's much faster now! However, similar to the brute force, the time complexity is still O(n)
.
Why Is This?
Well, if n
is the length of the string, we'll end up making n/2
swaps. But remember, Big O Notation isn't about the raw number of operations required for an algorithm-- it's about how the number scales with the input.
So despite requiring half the number operations-- a 4
-character string would require 2
swaps with the two-pointer method. But an 8
-character string would require 4
swaps. The input doubled, and so did the number of operations.
Final Solution
function reverseString(str) {
let strArr = str.split("");
let start = 0;
let end = str.length - 1;
while (start <= end) {
const temp = strArr[start];
strArr[start] = strArr[end];
strArr[end] = temp;
start++;
end--;
}
return strArr.join("");
}
Top comments (20)
This is incorrect, and why this is a non-trivial task.
A string represents text which is formed of graphemes, which are formed by combining character sequences in unicode.
Which means that in order to reverse a textual string properly you need to identify the graphemic units which need to be reordered, separate them, and then recombine.
Which means that you can't think of a string as being an array of characters if you want to process text properly in Javascript. :)
Interesting and accurate, arrays and strings are clearly not the same.
I think the confusion may come because both arrays and strings share some methods and properties with the same name, and we can do some "array-like" things, like:
length
concat()
str[0]
-- character position access ( though, the correct approach should bestr.charAt()
)Also, arrays are mutable and strings aren't. so we can't do this:
str[1] = 'stuff'
Also, when using the native constructor, for instance,
new String('Sup dude')
each character is numerically indexed (like arrays), but in this case, even though we're using the built-in native constructor, it is not creating a string, instead, it creates an object. So, when using the string properties - length, concat, etc - JS implicitly does this boxing for us( under the hood it uses the String() native ). So we need to do str.toString() in order to get the actual string.Those are language specific methods, in fact theoretically, strings have length while arrays have size, you can concat strings while you join arrays and string[i] breaks up on most languages for obvious reasons.
It's a comparison of whole different data structures where I don't want to involve at all (that's all already wrote about) but i feel the need to clarify this.
Thanks pentacular and Diego, these are really great points that I neglected to touch on. I'll add a bit into the tutorial and video to emphasize the distinctions.
You're welcome. :)
You did a great job Jake, we're all in this endless learning process! So keep up the good work man! :-)
Appreciate the kind words!
This is something I knew intuitively, but never thought of explicitly. Are there any resources you recommend that covers tips, tricks, gotchas for text processing in JS?
Begin with JS data structures, then search for string related API on JavaScript. Note that JavaScript lacks static typing so sometimes you can call a method that deals with strings on a non-string data type (same with other data types and language pre-defined methods). At this point you don't know what it does in background for example when performing string split, but you can also dig deeper if you want.
Yes, absolutely!
str.split('').reverse()
BTW, this doesn't work for surrogate pairs:
It's better to use spread syntax:
Does it always work correctly? I mean
Normally, I would rather trust this library -- npmjs.com/package/runes2
good
python
string.split().reverse().join()
Never reinvent the wheel :)
Ruby -> "string".reverse stonks
Lol Ruby does some things so much simpler. Still itβs great to be able to do something manually!
Plenty of ways to reverse a string thats a lot of wheels. π
This is the kind of thought process I absolutely need to improve. βHow can I optimize this procedure?β I need to better understand data structures to improve time/space complexity. Great read!!