algoadvance

Leetcode 917. Reverse Only Letters

Problem Statement

Given a string s, reverse the string according to the following rules:

1. All the characters that are not English letters remain in their original positions.
2. All the English letters (lowercase or uppercase) should be reversed.

Return s after reversing it.

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!”

Clarifying Questions

1. Q: Can the string s be empty?
   A: Yes, an empty string is a valid input and should be handled.

2. Q: Are there any constraints on the length of the string?
   A: The string length will be between 1 and 100.

3. Q: Are the non-letter characters limited to specific ones like -, =, etc.? A: No, any character that is not a letter should remain in its position.

Strategy

1. Use a two-pointer approach to traverse the string from both ends:
   • Initialize two pointers, one at the beginning (left) and one at the end (right) of the string.
   • Move these pointers towards each other.
2. While left pointer is less than right pointer:
   • If the character at left is not a letter, move the left pointer to the right.
   • If the character at right is not a letter, move the right pointer to the left.
   • If both characters are letters, swap them and then move both pointers.
3. Continue until the two pointers meet or cross.
4. Return the modified string.

Code

#include <iostream>
#include <string>
#include <cctype>

std::string reverseOnlyLetters(std::string s) {
    int left = 0;
    int right = s.length() - 1;
    
    while (left < right) {
        // Move left pointer to the right if not a letter
        if (!std::isalpha(s[left])) {
            left++;
        }
        // Move right pointer to the left if not a letter
        else if (!std::isalpha(s[right])) {
            right--;
        }
        // Both are letters, so we swap them
        else {
            std::swap(s[left], s[right]);
            left++;
            right--;
        }
    }
    
    return s;
}

// Test cases
int main() {
    std::string s1 = "ab-cd";
    std::string s2 = "a-bC-dEf-ghIj";
    std::string s3 = "Test1ng-Leet=code-Q!";
    
    std::cout << reverseOnlyLetters(s1) << std::endl; // Output: "dc-ba"
    std::cout << reverseOnlyLetters(s2) << std::endl; // Output: "j-Ih-gfE-dCba"
    std::cout << reverseOnlyLetters(s3) << std::endl; // Output: "Qedo1ct-eeLg=ntse-T!"
    
    return 0;
}

Time Complexity

• Time Complexity: O(N), where N is the length of the string. We traverse each character at most once using the two-pointer approach.
• Space Complexity: O(1), since we are modifying the string in place and not using any extra space proportional to the input size.

This approach optimally handles the problem by using a clear and efficient strategy, making it suitable for the given constraints.

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?