The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

Reversing a string means, rearranging the characters such that the last character becomes the first, the last-but-one character becomes the second, the third-to-the-last character becomes third; and so on.

Example:

Input:  "The Strongest Army in the World"
Output:  "dlroW eht ni ymrA tsegnortS ehT"

The number of characters in this example is odd. This means, the middle (center) character will not change its position. If the number of characters is even, there will be two middle (center) characters that will be swapped.

An array string can be reversed, using the temporary-array-technique, two pointers or single pointer.

Reversing a String using Temporary Array String in O(n) Time and O(n) Space

Here is the brute-force (naive) approach.

This involves:

- Creating a temporary string (array) of same size as the original string;
- copying all characters from original string to temporary string (array), in reverse order;
- and finally, copying all the characters from temporary string, back to the original string.

The algorithm essentially, takes the last character and puts as the first character, takes the last-but-one character and puts as the second character, takes the third-to-the-last character and puts as the third character; and so on. This swapping continues until the middle (center) of the array is reached. If the number of characters in the array is odd, then the middle (center) character is not swapped.

With zero based indexing, the swapping statement is:

     tempStr[i] = str[N - i - 1];

where i is the iterating index from 0, and N is the length (size) of the array string.

When i=0, "tempStr[0] = str[N - 0 – 1];" => "tempStr[0] = str[N – 1];"
When i=1, "tempStr[1] = str[N - 1 – 1];" => "tempStr[1] = str[N – 2];"
When i=2, "tempStr[2] = str[N - 2 – 1];" => "tempStr[1] = str[N – 3];"

The following program illustrates this (read through the code and comments, reading the main function first):

#include 

void reverseString(char str[], int N) {
    // Temporary array string to store characters
    // in reversed order
    int tempStr[N+1];
    tempStr[N] = '\0';
  
    // Copy all characters from original string
    // to tempStr in reverse order
    for(int i = 0; i < N; i++)
        tempStr[i] = str[N - i - 1];
  
    // Copy caracters back to original string
    for(int i = 0; i < N; i++)
        str[i] = tempStr[i];
}

int main(int argc, char **argv)
{
    int N = 0;    //length (size) of string to be determined in function below
    char stri[] = "The Strongest Army in the World";    //string for reversal
    
    char *ptr = stri;
    while (*ptr != '\0') {    //in C a string ends with '\0', which should not be counted
        ptr++; 
        N += 1;
    }

    reverseString(stri, N);
    
    // Print reverse characters in tempStr
    for(int i = 0; i < N; i++) 
        printf("%c ", stri[i]);
    printf("\n");
    
    return 0;
}

The output is:

    "d l r o W   e h t   n i   y m r A   t s e g n o r t S   e h T" 

achieved in O(N) time and O(N) space for the for-loops and string arrays respectively. The time complexity is actually O(3N) and the space complexity is actually O(2N). However, the coefficient (multiplier) is usually omitted when quoting the complexity. The time complexity is actually O(3N) for the two for-loops and the one while-loop.

The given string array and the string array in the reverseString() function parameter list (parentheses) are the same one string (reference).

Reversing a String using Two Pointers in O(n) Time and O(n) Space

Two pointers refer to left (i) and right (j) indexes, such that left points to the start of the array and right points to the end of the array, initially.

While the left pointer is less than the right pointer, swap the characters at these two positions. After each swap, increment the left pointer and decrement the right pointer to move towards the center of the array. This will swap all the characters in the first half with their corresponding characters in the second half.

The following program illustrates this (read through the code and comments):

#include 

// Helper function to swap two numbers
void swap(char *a, char *b) {
    char temp = *a;    //temporary single variable and not temporary array
    *a = *b;
    *b = temp;
}

// function to reverse a String
void reverseString(char str[], int n) {
    int left = 0, right = n - 1;

    // Iterate till left would almost equal right
    while (left < right) {
        swap(&str[left], &str[right]);

        // Increment the left pointer
        left++;
        // Decrement the right pointer
        right--;
    }
}

int main(int argc, char **argv)
{
    int n = 0;    //length (size) of string to be determined in function below
    char stri[] = "The Strongest Army in the World";    //string for reversal
    
    char *ptr = stri;
    while (*ptr != '\0') {    //in C a string ends with '\0', which should not be counted
        ptr++; 
        n += 1;
    }

    reverseString(stri, n);
    
    // Print reverse characters in tempStr
    for(int i = 0; i < n; i++) 
        printf("%c ", stri[i]);
    printf("\n");
    
    return 0;
}

Note the use of the swap() helper function, where char *a from the swap() function corresponds to &char[left] in the called function, and char *b from the swap() function corresponds to &char[right] in the called function. The whole program has just one array, given in the main section. The output is:

    d l r o W   e h t   n i   y m r A   t s e g n o r t S   e h T 

achieved in O(n) time and O(n) space, for the for-loop and array respectively. O(n) space refers to the only array string, which is the input array string. The while-loop in the reverseString() function takes precisely O(1/2N) time, but the ½ (coefficient) has to be omitted when quoting the complexity. The time complexity is actually O(1½N), but 1½ would be omitted when quoting complexity

Reversing a String using Single Pointer in O(n) Time and O(n) Space

This approach iterates over the first half of the array string and swaps each character with its corresponding character of the second half. So, while iterating over the first half, any character at index i is swapped with the character at index (n - i – 1). If the number of characters in the given array string is odd, the center character is not swapped. left (i) is the single pointer. The following program illustrates this (read through the code and comments):

#include 

void reverseString(char str[], int n) {
    // swap str[i] with str[n - i - 1]
    for (int i = 0; i < n / 2; i++) {
        int tempStr = str[i];    //temporary single variable and not temporary array
        str[i] = str[n - i - 1];
        str[n - i - 1] = tempStr;
    }
}

int main(int argc, char **argv)
{
    int n = 0;    //length (size) of string to be determined in function below
    char stri[] = "The Strongest Army in the World";    //string for reversal
    
    char *ptr = stri;
    while (*ptr != '\0') {    //in C a string ends with '\0', which should not be counted
        ptr++; 
        n += 1;
    }

    reverseString(stri, n);
    
    // Print reverse characters in tempStr
    for(int i = 0; i < n; i++) 
        printf("%c ", stri[i]);
    printf("\n");
    
    return 0;
}

n / 2 is integer division. This division discards the remainder. If the number of characters in the array is odd, say 9 for example, then the center (middle) index would be 4, whose character is not swapped. If the number of characters is even, say 8 for example, then the almost center (middle) left index would be 3, whose character has to be swapped with the almost center (middle) right character of index 4.

The output is:

    d l r o W   e h t   n i   y m r A   t s e g n o r t S   e h T 

achieved in O(n) time and O(n) space, for the for-loop and array respectively. O(n) space refers to the only array, which is the input array. The for-loop takes precisely O(1/2N) time, but the ½ has to be omitted when quoting the complexity.

Thanks for reading.