Skip to main content

Reverse Only Letters

Problem Description​

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

  • All the characters that are not English letters remain in the same position.
  • All the English letters (lowercase or uppercase) should be reversed.

Return s after reversing it.

Examples​

Example 1:

Input: s = "ab-cd"
Output: "dc-ba"

Example 2:

Input: s = "a-bC-dEf-ghIj"
Output: "j-Ih-gfE-dCba"

Constraints​

  • 1≤s.length≤1001 \leq s.length \leq 100
  • s consists of characters with ASCII values in the range [33, 122].
  • s does not contain '\"' or '\\'.

Solution for Reverse Only Letters​

Approach: Stack of Letters​

Intuition and Algorithm​

Collect the letters of S separately into a stack, so that popping the stack reverses the letters. (Alternatively, we could have collected the letters into an array and reversed the array.)

Then, when writing the characters of S, any time we need a letter, we use the one we have prepared instead.

Code in Different Languages​

Written by @Shreyash3087
class Solution {
public:
string reverseOnlyLetters(string S) {
stack<char> letters;
for (char c : S)
if (isalpha(c))
letters.push(c);

string ans;
for (char c : S) {
if (isalpha(c))
ans += letters.top(), letters.pop();
else
ans += c;
}

return ans;
}
};

Complexity Analysis​

Time Complexity: O(N)O(N)​

Reason: where N is the length of S.

Space Complexity: O(N)O(N)​

Approach: Reverse Pointer​

Intuition​

Write the characters of S one by one. When we encounter a letter, we want to write the next letter that occurs if we iterated through the string backwards.

So we do just that: keep track of a pointer j that iterates through the string backwards. When we need to write a letter, we use it.

Code in Different Languages​

Written by @Shreyash3087
#include <string>
#include <cctype>
#include <sstream>

class Solution {
public:
std::string reverseOnlyLetters(std::string S) {
std::stringstream ans;
int j = S.length() - 1;
for (int i = 0; i < S.length(); ++i) {
if (std::isalpha(S[i])) {
while (!std::isalpha(S[j]))
j--;
ans << S[j--];
} else {
ans << S[i];
}
}

return ans.str();
}
};

Complexity Analysis​

Time Complexity: O(N)O(N)​

Reason: where N is the length of S.

Space Complexity: O(N)O(N)​

Video Solution​

References​


Authors:

Loading...