Reverse Only Letters

Posted: 15 Mar, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You are given a string, ‘S’. You need to reverse the string where characters that are not an alphabet stay in the same place, and the rest reverse their positions.

Eg: “a-bcd” becomes “d-cba”

Input Format:
The first line of the input contains ‘T’ denoting the number of test cases.

The first line of each test case contains a string ‘S’.
Output Format:
For every test case, we need to print the reversed string in a new line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
0 <= |S| <= 5000

Where |S| denotes the length of string 'S'.

Time Limit: 1 Sec
Approach 1

Approach: Just like in order to reverse a string ‘S’ = “abcd”, we can can swap(S[0], S[3]) and swap(S[1],S[2]) to get new string “dcba”.

 

Similarly in this problem, we do the same using two pointers while ignoring the non-letter characters.

 

Eg: S = “a-bcd” we swap(S[0], S[4]) and swap(S[2], S[3]) to get the result.

 

Algorithm:

  1. In the given string what we can do is maintain two variables one pointer to the 0th position and the other pointing to the ‘N - 1’ position.
  2. If both have letters we swap them and increment the first pointer and decrement second.
  3. Else if the first pointer has a non-letter we just increment it and if the second pointer has a non-letter we decrement it.
  4. We continue it till the first pointer is less than the second pointer.
Try Problem