Sponsored
Sponsored
Using a two-pointer technique, we can efficiently reverse only the letters in the string. One pointer starts from the beginning and the other from the end. We swap letters when both pointers are on valid letters. If a pointer is on a non-letter, it moves until it finds a letter. The process continues until the two pointers meet or cross each other.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), as we are modifying the string in place.
1#include <iostream>
2#include <cctype>
3
4std::string reverseOnlyLetters(std::string s) {
5 int left = 0, right = s.length() - 1;
6 while (left < right) {
7 while (left < right && !isalpha(s[left])) left++;
8 while (left < right && !isalpha(s[right])) right--;
9 if (left < right) std::swap(s[left++], s[right--]);
10 }
11 return s;
12}
13
14int main() {
15 std::string s = "a-bC-dEf-ghIj";
16 std::cout << reverseOnlyLetters(s) << std::endl;
17 return 0;
18}This C++ solution is similar to the C version, using two pointers and STL function std::swap() for swapping. The isalpha() function checks if characters are letters.
This approach uses a stack to collect all the letters in the string and then reinserts them in reverse order while iterating through the original string.
Time Complexity: O(n), for iterating through the string twice.
Space Complexity: O(n), for storing letter characters in the stack.
1#include
C solution employs a manual stack using an array to reverse letters. The letters are first pushed into the stack and then popped off when reinserting into the original string.