917. Reverse Only Letters
Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 59.4%
Problem Breakdown
The problem requires reversing only the letters in a given string S, while keeping all non-letter characters (such as punctuation and spaces) in their original positions. The input is a string S with a length constraint of up to 100 characters, and each character has an ASCII code between 33 and 122.
Inputs:
- A single string
S.
Outputs:
- A string where all letters are reversed in order, but non-letter characters remain in their original positions.
Implicit Constraints or Edge Cases:
- The string can be empty.
- The string may contain only non-letter characters.
- The string may contain a mix of uppercase and lowercase letters.
Intuition
A brute-force approach would involve iterating through the string twice: once to collect all the letters, and another time to construct the result by placing the collected letters back in reverse order while keeping non-letter characters in their original positions. This approach is inefficient because it requires two passes over the string and additional space to store the letters.
A better approach involves using a two-pointer technique. We can initialize two pointers: one at the beginning (left) and one at the end (right) of the string. We then move these pointers towards each other, swapping letters when both pointers point to letters, and skipping non-letter characters by moving the respective pointer forward or backward.
Approach
- Initialize two pointers,
leftat the start of the string andrightat the end. - While
leftis less thanright, do the following:- If both
S[left]andS[right]are letters, swap them and move both pointers inward. - If
S[left]is not a letter, incrementleft. - If
S[right]is not a letter, decrementright.
- If both
- Continue this process until the two pointers meet or cross each other.
- Return the modified string.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string. Each character is processed at most once.
- Space Complexity: O(1) if we consider the input and output as part of the space complexity, otherwise O(n) due to the creation of a list for the result.
Solution
def reverseOnlyLetters(S: str) -> str:
S = list(S) # Convert string to list for easy swapping
left, right = 0, len(S) - 1
while left < right:
if S[left].isalpha() and S[right].isalpha():
S[left], S[right] = S[right], S[left]
left += 1
right -= 1
elif not S[left].isalpha():
left += 1
elif not S[right].isalpha():
right -= 1
return ''.join(S)
Edge Cases Handled
- Empty String: The function will correctly return an empty string if the input is empty.
- String with No Letters: If the string contains no letters, it will be returned unchanged.
- String with Mixed Characters: The function handles strings with a mix of uppercase and lowercase letters, as well as non-letter characters.