Reverse an array without affecting special characters - GeeksforGeeks

Reverse an array without affecting special characters - GeeksforGeeks

Reverse an array without affecting special characters

Given a string, that contains special character together with alphabets ('a' to 'z' and 'A' to 'Z'), reverse the string in a way that special characters are not affected.

Examples:

Input:   str = "a,b$c"  Output:  str = "c,b$a"  Note that $ and , are not moved anywhere.    Only subsequence "abc" is reversed    Input:   str = "Ab,c,de!$"  Output:  str = "ed,c,bA!$"  

We strongly recommend you to minimize your browser and try this yourself first.

Simple Solution:
1) Create a temporary character array say temp[].
2) Copy alphabetic characters from given array to temp[].
3) Reverse temp[] using standard string reversal algorithm.
4) Now traverse input string and temp in a single loop. Wherever there is alphabetic character is input string, replace it with current character of temp[].

Efficient Solution:
Time complexity of above solution is O(n), but it requires extra space and it does two traversals of input string.
We can reverse with one traversal and without extra space. Below is algorithm.

1) Let input string be 'str[]' and length of string be 'n'  2) l = 0, r = n-1  3) While l is smaller than r, do following      a) If str[l] is not an alphabetic character, do l++      b) Else If str[r] is not an alphabetic character, do r--      c) Else swap str[l] and str[r]  

Below is C++ implementation of above algorithm.

Read full article from Reverse an array without affecting special characters - GeeksforGeeks