Reverse Only Letters

Problem Statement

Given a string s, you are required to reverse the string in a way that only the alphabetical letters (both lowercase and uppercase) are reversed, while all other characters retain their original positions in the string. At the end of the transformation, the string should be returned in its new form with the described alterations.

Examples

Example 1

Input:

s = "ab-cd"

Output:

"dc-ba"

Example 2

Input:

s = "a-bC-dEf-ghIj"

Output:

"j-Ih-gfE-dCba"

Example 3

Input:

s = "Test1ng-Vultr=code-Q!"

Output:

"Qedo1ct-edul=rngT-T!"

Constraints

• 1 <= s.length <= 100
• s consists of characters with ASCII values in the range [33, 122].
• s does not contain '\"' or '\'.

Approach and Intuition

The problem is a classic example of string manipulation with specific conditions on which characters should be moved and which should remain fixed. The task involves handling a string and reversing only the subset of characters that are English letters, while keeping symbols, numbers, and other characters in the same sequential position as they were originally. Here's a straightforward approach using this understanding:

1. Traverse the input string to collect all the English letters and save them separately.

2. Reverse the collected English letters since these are the only characters that need to be reordered.

3. Iterate over the original string again. For each character:

   • If the character is an English letter, replace it with the next English letter from the reversed collection.
   • If it is not an English letter, just append it to the result as it is.

4. Construct the output based on the positions of characters and the reversed order of English letters.

By applying this method, all non-English letters are simply bypassed in the reordering process, thus satisfying the condition of keeping them at the same indices as they were in the original input string, while effectively reversing the sequence of English letters amidst them.

Solutions

class Solution {
    public String reverseLettersInString(String inputStr) {
        StringBuilder result = new StringBuilder();
        int backwardIdx = inputStr.length() - 1;
        for (int forwardIdx = 0; forwardIdx < inputStr.length(); ++forwardIdx) {
            if (Character.isLetter(inputStr.charAt(forwardIdx))) {
                while (!Character.isLetter(inputStr.charAt(backwardIdx)))
                    backwardIdx--;
                result.append(inputStr.charAt(backwardIdx--));
            } else {
                result.append(inputStr.charAt(forwardIdx));
            }
        }

        return result.toString();
    }
}