Reverse Only Letters

Easy
0/40
Average time to solve is 15m
profile
Contributed by
12 upvotes
Asked in companies
AppleOYOPayPal

Problem statement

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”

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
a-bcd
!s-cx
Sample Output 1:
d-cba
!x-cs
Explanation Of Sample Input 1:
In the first test case:
“a-bcd” after removing non-letter will be “abcd”.
Reversing “abcd” will get “dcba”.
Placing non-letters in the correct position in “dcba”, we get: “d-cba”.

In the second test case:
“!s-cx” after removing non-letter will be “scx”.
Reversing “scx” will get “xcs”.
Placing non-letters in the correct position in “xcs”, we get: “!x-cs”.
Sample Input 2:
2
a-bC-dEf-ghIj
Qedo1ct-eeLg=ntse-T!
Sample Output 2:
j-Ih-gfE-dCba
Test1ng-Leet=code-Q!
Explanation Of Sample Input 2:
In the first test case:
“a-bC-dEf-ghIj” after removing non-letter will be “abCdEfghlj”.
Reversing “abCdEfghlj” will get “jlhgfEdCba”.
Placing non-letters in the correct position in “jlhgfEdCba”, we get: “j-Ih-gfE-dCba”.

In the second test case:
“!s-cx” after removing non-letter will be “Qedo1ct-eeLg=ntse-T!”.
Reversing “QedocteeLgntseT” will get “TestngLeetcodeQ”.
Placing non-letters in the correct position in “TestngLeetcodeQ”, we get: “Test1ng-Leet=code-Q!”.
Hint

Try to use variables to track the positions of last and first alphabets.

Approaches (1)
Two Pointer Approach

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.
Time Complexity

O(N), where ‘N’ is the length of the string.

 

We are only iterating in the string so, the time complexity is O(N).

Space Complexity

O(1).

 

We are only using the original string and not creating a new string.

Code Solution
(100% EXP penalty)
Reverse Only Letters
Full screen
Console