How to Reverse a String Keeping Special Characters in Place

Introduction

This article will show how to reverse a string while keeping special characters. We want those characters to be unaffected and keep their original positions. We will implement a solution using the Java language.

Reverse a String While Keeping Special Characters Problem

Imagine a String containing both alphabetic and special characters. We want to obtain a new String with all the positions of alphabetic characters reversed and those of special ones unaltered.

For example, imagine we have the following String:

String toReverse = "abcd%ef";

We want to obtain:

"fedc%ba"

Reverse a String While Keeping Special Characters Algorithm

We have already seen a couple of algorithms to reverse a string. The second of the solutions described in that article is optimized in terms of space efficiency. We will use it here as a base to implement the above-described problem.

The solution is very similar to the one described in the above article. The only difference is that we condition the shifting of left and right array positions by a check on the character involved in those positions. If it is not alphabetic for the left index we increment it, and if it is not alphabetic for the right one we decrement it. The algorithm can be described by the following steps:

• We start a loop from the first position of the sequence of characters on the left onwards and at the same time from the last position on the right backwards.
• We increment the left and decrease the right index of the loop by one until the left index is less than the right one
• In each step of the loop, if the current character on the left is not alphabetic we increment the left index and if the current character on the right is not alphabetic we decrement the right index. In both cases, we skip the current step of the loop and continue
• If the above conditions are not met we exchange the left and right values

The following JUnit test case shows the ideas above described:

@Test
public void reverseStringKeepSpecialTest() throws Exception {

    String toReverse = "abcd%ef";
    char[] chArray = toReverse.toCharArray();

    int i = 0, j = chArray.length - 1;
    while (i < j) {
        if (!Character.isAlphabetic(chArray[i])) {
            ++i;
        }
        if (!Character.isAlphabetic(chArray[j])) {
            --j;
        }
        char temp = chArray[i];
        chArray[i] = chArray[j];
        chArray[j] = temp;
        ++i;
        --j;
    }

    String reversed = String.valueOf(chArray);
    System.out.println(reversed);
    for (int n = 0, m = chArray.length - 1; n < chArray.length; n++, m--) {
        if (!Character.isAlphabetic(chArray[n])) {
            ++n;
        }
        if (!Character.isAlphabetic(chArray[m])) {
            --m;
        }
        assertEquals(toReverse.toCharArray()[n], chArray[m]);
    }
    assertTrue(!Character.isAlphabetic(toReverse.toCharArray()[4]));
}

Performance Considerations

The time complexity of the above algorithm is O(n).

Conclusion

In this article, we have seen how to reverse a String containing special characters, and at the same time keep those special characters in place. The example code is available on GitHub.