[Solved] Reverse String Without Affecting Special Characters

Problem Statement: You have given a string. There can have multiple special characters inside the string. Write a program to reverse the given string. The position of the special characters should not be changed.

Example:

Input: 'abc/defgh$ij'
Output: 'jih/gfedc$ba'

Algorithm:
Here is a simple algorithm to solve this problem to reverse string without affecting special characters

• Convert given string into a list (or array) such that every character in the string will be one element in the list.
• Set the two pointers at the beginning of the list (says i) and at the end of the list (says j)
• repeat while i<j:
  • if list[i] is a special character, increment i by 1
  • else if list[j] is a special character, decrement j by 1
  • else (list[i] and list[j] are alphabets) swap list[i] and list[j], increment i by 1 , decrement j by 1

Python Program:

strSample='abc/defgh$ij'

#convert string into list
listSample=list(strSample)

i=0
j=len(listSample)-1

while i<j:
    if not listSample[i].isalpha():
        i+=1
    elif not listSample[j].isalpha():
        j-=1
    else:
        #swap the element in the list 
        #if both elements are alphabets
        listSample[i], listSample[j]=listSample[j], listSample[i]
        i+=1
        j-=1

#convert list into string 
#by concatinating each element in the list
strOut=''.join(listSample)
print(strOut)

Output:

jih/gfedc$ba

An isAlpha() is the character method that returns true if the character is an alphabet. Otherwise (if it is a special character), it returns false.

In Python, we can reverse the string with a single line of code. But, this is a special case where we don’t want to change the position of the special characters.

Similarly, you can solve this problem in C/C++ or Java.

This question was asked in the Oracle interview.

Complexity:

We are traversing each character in the string at once. In the worst case, the time complexity is O(n), where n is the size of the given string.

We can do the in-place swapping of the characters of the string. So, it does not require any extra space. (In the case of Python, it’s not possible to swap the characters inside the string. So, we are obligated to use the list. This causes extra memory space.)

This is the simple solution to reverse string without affecting special characters. Practice solving more of such coding questions to improve your programming skills.