This problem looks busy at first, but the accepted solution is built around one steady invariant. For 917. Reverse Only Letters, the solution in this repository is mainly a stack solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: stack.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are reverseOnlyLetters.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- The stack stores unfinished context, which is usually the cleanest way to handle nested or monotonic structure.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(N), where N is the length of S.
- Space: O(N).
Guide
C++ Solution
Your submission
The accepted solution
01/**
02Given a string S, return the "reversed" string where all characters that are not a letter stay in the same place, and all letters reverse their positions.
03
04
05
06Example 1:
07
08Input: "ab-cd"
09Output: "dc-ba"
10Example 2:
11
12Input: "a-bC-dEf-ghIj"
13Output: "j-Ih-gfE-dCba"
14Example 3:
15
16Input: "Test1ng-Leet=code-Q!"
17Output: "Qedo1ct-eeLg=ntse-T!"
18
19
20Note:
21
22S.length <= 100
2333 <= S[i].ASCIIcode <= 122
24S doesn't contain \ or "
25**/
26
27/**
28Approach 2: Reverse Pointer
29Intuition
30
31Write the characters of S one by one.
32When we encounter a letter,
33we want to write the next letter that occurs if we iterated through the string backwards.
34
35So we do just that:
36keep track of a pointer j that iterates through the string backwards.
37When we need to write a letter, we use it.
38**/
39
40/**
41Complexity Analysis
42Time Complexity: O(N), where N is the length of S.
43Space Complexity: O(N).
44**/
45
46//Runtime: 4 ms, faster than 100.00% of C++ online submissions for Reverse Only Letters.
47//Memory Usage: 9 MB, less than 40.00% of C++ online submissions for Reverse Only Letters.
48class Solution {
49public:
50 string reverseOnlyLetters(string S) {
51 string ans(S.size(), 'a');
52
53 //fill with non-alpha characters
54 for(int i = 0; i < S.size(); i++){
55 if(!isalpha(S[i])){
56 ans[i] = S[i];
57 }
58 }
59
60 int j = S.size()-1;
61 for(int i = 0; i < S.size(); i++){
62 if(!isalpha(S[i])){
63 continue;
64 }
65 //the vector is initialized with 'a'!
66 //use while rather than if!
67 //skip all filled position
68 while(!isalpha(ans[j])){
69 j--;
70 }
71 ans[j--] = S[i];
72 }
73
74 return ans;
75 }
76};
77
78/**
79Approach 1: Stack of Letters
80Intuition and Algorithm
81Collect the letters of S separately into a stack,
82so that popping the stack reverses the letters.
83(Alternatively, we could have collected the letters into an array and reversed the array.)
84Then, when writing the characters of S, any time we need a letter, we use the one we have prepared instead.
85**/
86
87/**
88Complexity Analysis
89Time Complexity: O(N), where N is the length of S.
90Space Complexity: O(N).
91**/
92
93/**
94class Solution {
95public:
96 string reverseOnlyLetters(string S) {
97 string ans;
98 stack<char> letters;
99
100 for(char c : S){
101 if(isalpha(c)){
102 letters.push(c);
103 }
104 }
105
106 for(char c : S){
107 if(!isalpha(c)){
108 ans += c;
109 }else{
110 ans += letters.top();
111 letters.pop();
112 }
113 }
114
115 return ans;
116 }
117};
118**/Cost