In-place reverse of C-style string

Question

This is a question from the book "Cracking the Coding Interview".

Write code to reverse a C-Style String (C-String means that “abcd” is represented as five characters, including the null character )

Please review this code.

#include <iostream>

void inPlaceReverseString(char str[], int size)
{  
    int j = size - 2;
    int i;

    for (i = 0; i < (size-1)/2; ++i)
    {
        std::swap(str[i], str[j]);
        j--;
    }
    str[size - 1] = '\0';
}

int main()
{
    char str[255];
    std::cout << "Enter String\n";
    std::cin.getline(str, 255);
    std::cout << "String: " << str << '\n';
    int size = 0;
    while (str[size] != '\0')
    {
        size++;
    }
    size++;
    inPlaceReverseString(str, size);
    std::cout << "Reversed String: " << str << '\n';
}

Answer 1

Because this is an attempt to answer an interview question, let's assume a hypothetical interviewer then asked you,

what would happen if I called your function using the following code:

...
char mylongstr[] = "This is my long string with lots of character.";
inPlaceReverseString(mylongstr, 7); // should reverse "This is"
cout << '"' << mylongstr << '"';
cout << " has " << strlen(mylongstr) << " characters\n";
...

It would print,

"i sihT" has 6 characters

That doesn't seem to make sense. Not only that, your function potentially clobbered the rest of my string, by writing \0 over the s in the word is.

Don't break expectations/convention with strings

@koblas mentioned to use the standard library function strlen().

strlen() returns the number of characters, not including the terminating \0 character, in the string passed to it. C and C++ string handling functions that take a count parameter generally expect that count refers to the number of characters to work on.

But the size parameter to inPlaceReverseString() breaks that expectation. I think you're overthinking the C-style string's terminating \0 character.

For interview questions (as well as coding in general), start with the simplest thing that can work and meets the specifications

Note that the interview question you quoted said, "write code to reverse a C-Style String", not "write code to reverse a specified number of characters in a C-Style String". For an interview-type question like this, rather than pass the length of the string as a parameter, just discover the length of the string within your function:

void inPlaceReverseString(char str[])
{  
    for (int i = 0, int j = strlen(str) - 1; i < j; ++i, --j) {
        std::swap(str[i], str[j]);
    }
}

Note also that I slightly changed the loop-terminating logic, by checking i < j. This makes the logic a bit easier to read, making it obvious that when the indexes i and j pass each other, there's no more replacement to be done.

---

Now, if you still want to have a length parameter (or are asked to extend the simple answer I wrote above), a couple suggestions:

1. Use a parameter name such as num, len, or even n, as opposed to size. This is really pedantic on my part, but size tends to suggest memory sizes, as opposed to length of strings or number of characters.

2. Use size_t as the type of the length parameter. This is an unsigned type, and conforms with the rest of C-style string functions that have a length/number parameter.

3. Don't write a terminating \0 after the in place reversal.

4. Even if a length is specified, you should still check for a terminating \0 character within the string.

So, a possible implementation of the answer would look something like:

void inPlaceReverseString(char str[], size_t num)
{
    int len = strlen(str);
    if (len < num) {
        // length of 'str' is less than 'num'. How to handle? ...
    }
    for (int i = 0, int j = strlen(str) - 1; i < j; ++i, --j) {
        std::swap(str[i], str[j]);
    }
}

Now, the original hypothetical question asked by the hypothetical interviewer at the start of this answer would work:

...
char mylongstr[] = "This is my long string with lots of character.";
inPlaceReverseString(mylongstr, 7); // should reverse "This is"
cout << '"' << mylongstr << '"';
cout << " has " << strlen(mylongstr) << " characters\n";
...

would print:

"si sihT my long string with lots of character." has 47 characters

Answer 2

You should look at using the strlen() function. Use sizeof(str) so you don't have constants in two places.

int main()
{
    char str[255];
    std::cout << "Enter String\n";
    std::cin.getline(str, sizeof(str));
    std::cout << "String: " << str << '\n';
    inPlaceReverseString(str, strlen(str) + 1);
    std::cout << "Reversed String: " << str << '\n';
}

For your loop: Put everything in the loop iteration portion. You initialize some variables inside and outside the loop, better if it's all in one place.

for (int i = 0, j = size - 2; i < (size-1)/2; ++i, --j) {
    std::swap(str[i], str[j]);
}

Answer 3

Here's a few things to consider:

You can remove the j variable from your loop

You only use it once. Instead you can write str[size - 1 - i]. This saves you two lines of code, and the less code you have, the easier it usually is to focus on what a function does and to reason about it.

var-- is slower than --var

If you wanted to keep your j, you could change that second line of the loop to --j. This isn't a major speed improvement, but if you're preparing for an interview, it's probably a good way to show that you know what you're doing. This article does a fairly good job at explaining why this is, but don't bother too much trying to understand the messy details. Just know that it's a thing.

You don't need to manually append \0

Reversing a string does not change its length, so the null-character will be at the same byte it was before, thus you can just leave it be.

Conclusion

Considering the three points above, and the fact that size can be used as if it was a local variable to your function, you could write the function like this:

void inPlaceReverseString(char str[], int length) {
    int i;
    --length;

    for (i = 0; i < (length)/2; ++i) {
        std::swap(str[i], str[length - i]);
    }
}

As you can see, you can decrement the size variable in place as you only ever need size-1. That's one operation we've taken out of the loop. If you want to take this one step further, you can save size/2 into its own variable to avoid having to divide it by 2 in every loop, but that'd make the code more complex and you'd only want to do that if speed is really crytical. In an interview, you could possibly mention this as an option if future benchmarks show that the function acts as a bottleneck.

Also note that I have changed size to length. The reason for that is that size usually refers to the size of the character buffer (255 in your example), not the length of the string it contains. Also the length of a string usually doesn't count the null-character at the end, so I took the liberty to change that as well. That's important because the size you calculate in main does include the null-character.

Answer 4

Outside of <iostream>, your code looks like C rather than C++. That isn't necessarily bad, since you're dealing with C style strings, but you could also consider alternatives.

C style reversing

The function seems to take an array as its first argument, but it's actually completely equivalent to:

void inPlaceReverseString(char* str, int size);

So you don't need to use array indexing and may as well manipulate pointers directly, which is more traditional, concise and readable:

void inPlaceReverseString(char* str, int size) {
    char* end = str + size;
    while (str < --end) std::swap(*str++, *end);
}

Since you use std::swap, you could as well use other small C++ language or library features (conventions included):

void inPlaceReverseString(char* first, int size) {
    auto last = std::next(first, size);
    while (first < --last) std::swap(*first++, *last);
}

C++ style reversing

Since std::swap(*first++, *last) can be replaced by std::iter_swap(first++, last), you could have chosen the latter, which is arguably more readable. That substitution is possible because pointers are iterators in C++. Which also leads us to what an in place reversing function would look like in C++:

template <typename Iterator>
void reverse(Iterator first, Iterator last) {
    while (first < --last) std::iter_swap(first++, last);
}

This is rather interesting, because it can reverse a vector or a list as well, or anything that has a bidirectional iterator interface actually. It will soon be possible to constrain the argument type with a concept (voted for C++20):

// given a Bidirectional_iterator concept
template <Bidirectional_iterator Iterator>
void reverse(Iterator first, Iterator last) {
    while (first < --last) std::iter_swap(first++, last);
}

If we are given a c_style string and its size, we can then call reverse this way:

reverse(str, str+size);

Of course, it could be better to use a RAII container over a C string, but since it's part of the question...