algoadvance

Leetcode 917. Reverse Only Letters

Problem Statement

You are given a string s which consists of lowercase and uppercase letters. Reverse only the letters and leave all other characters at their original positions.

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-Leet=code-Q!”
• Output: “Qedo1ct-eeLg=ntse-T!”

Constraints:

• 1 <= s.length <= 100
• s consists of characters with ASCII values in the range [33, 122].

Clarifying Questions

1. Does the input string include symbols, digits, and spaces?
   • Answer: The problem statement implies that s consists of various characters, not limited to letters.
2. Should the case sensitivity of letters be maintained?
   • Answer: Yes, maintain the case sensitivity (lowercase should remain lowercase and uppercase should remain uppercase).
3. Are there any special performance requirements?
   • Answer: None specified, but an efficient solution is always desirable.

Strategy

1. Two-pointer Approach: Use two pointers, one starting from the beginning and the other from the end. Move both pointers towards the center of the string.
2. Swap Letters: When both pointers point to a letter, swap the letters.
3. Skip Non-Letters: If a pointer points to a non-letter, move that pointer inward without making a swap.
4. Stop Condition: Continue the process until the two pointers cross each other.

Code

public class ReverseOnlyLetters {
    public String reverseOnlyLetters(String s) {
        char[] arr = s.toCharArray();
        int left = 0;
        int right = arr.length - 1;
        
        while (left < right) {
            if (!Character.isLetter(arr[left])) {
                left++;
            } else if (!Character.isLetter(arr[right])) {
                right--;
            } else {
                char temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                left++;
                right--;
            }
        }
        
        return new String(arr);
    }

    public static void main(String[] args) {
        ReverseOnlyLetters solution = new ReverseOnlyLetters();
        System.out.println(solution.reverseOnlyLetters("ab-cd")); // "dc-ba"
        System.out.println(solution.reverseOnlyLetters("a-bC-dEf-ghIj")); // "j-Ih-gfE-dCba"
        System.out.println(solution.reverseOnlyLetters("Test1ng-Leet=code-Q!")); // "Qedo1ct-eeLg=ntse-T!"
    }
}

Time Complexity

• Time Complexity: O(n), where n is the length of the string. The two-pointer technique ensures that each character is processed at most once.
• Space Complexity: O(n), if considering the space required to store the character array. However, if the reversal is done in-place, the additional space used is constant, O(1).

This approach is efficient and fulfills the problem’s requirements effectively.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?