Reverse Only Letters
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

Question

Reverse Only Letters

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

Accepted Answer

Key idea - 2 pointer method
Approach - place one pointer p1 on start, 2nd pointer p2 on end. Move p1 to right and p2 to left unless we find a non special character for both, if found for both, swap the values pointed by p1 and p2.
Steps :
S1 : Pointer p1 at start and p2 at end index
S2 : while p1! = p2 and arr[p1] is special character, move p1 to right
S3 : while p1! = p2 and arr[p2] is special character, move p2 to left
S4 : Swap values pointed by index p1 and p2.
S5 : Follow above steps until p1 < p2.

Accepted Answer

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:

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.
If both have letters we swap them and increment the first pointer and decrement second.
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.
We continue it till the first pointer is less than the second pointer.

Space Complexity: O(1)Explanation:

O(1).

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

Time Complexity: O(n)Explanation:

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

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

Java (SE 1.8)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where 'N' is the length of the string 'S'.

*/



public class Solution {

    public static String reverseOnlyLetters(String s) {

        char[] ch = s.toCharArray();



        // Two pointers.

        int i = 0;

        int j = s.length() - 1;



        while (i < j) {



            if (!Character.isAlphabetic(ch[i])) {

                // Skipping non-letter.

                i++;

                continue;

            } else if (!Character.isAlphabetic(ch[j])) {

                // Skipping non-letter.

                j--;

                continue;

            }



            char temp = ch[i];

            ch[i] = ch[j];

            ch[j] = temp;



            i++;

            j--;

        }



        s = String.valueOf(ch);

        return s;

    }

}

Python (3.5)

'''
    Time Complexity: O(N)
    Space Complexity: O(1)

    Where 'N' is the length of the string 'S'.
'''

def swap(s, i, j):
    return ''.join((s[:i], s[j], s[i + 1:j], s[i], s[j + 1:]))

def reverseOnlyLetters(s):

    # Two pointers.
    i = 0
    j = len(s) - 1

    while(i < j):

        if(s[i].isalpha() is not True):
            # Skipping non-letter.
            i += 1
            continue
        elif(s[j].isalpha() is not True):
            # Skipping non-letter.
            j -= 1
            continue

        s = swap(s, i, j)
        i += 1
        j -= 1

    return s

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where 'N' is the length of the string 'S'.

*/



string reverseOnlyLetters(string & s) {



    // Two pointers.

    int i = 0;

    int j = s.size() - 1;



    while (i < j) {



        if (!isalpha(s[i])) {

            // Skipping non-letter.

            i++;

            continue;

        } else if (!isalpha(s[j])) {

            // Skipping non-letter.

            j--;

            continue;

        }



        swap(s[i], s[j]);

        i++;

        j--;

    }



    return s;



}

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:

Output Format:

Note:

Constraints:

Top PayU Payments Software Engineer interview questions & answers

Popular interview questions of Software Engineer

Top HR questions asked in PayU Payments Software Engineer