Lecture 71 :- Reverse Only Letters

To solve the "Reverse Only Letters" problem, you need to reverse the letters in a given string while keeping all other characters (digits, symbols, spaces) in their original positions.

Here's the C++ implementation to reverse only the letters in the string:

cppCopy code

#include <iostream> #include <string> bool isLetter(char c) {    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); } std::string reverseOnlyLetters(std::string s) {    int left = 0;    int right = s.length() - 1;    while (left < right) {        if (!isLetter(s[left])) {            left++;        } else if (!isLetter(s[right])) {            right--;        } else {            std::swap(s[left], s[right]);            left++;            right--;        }    }    return s; } int main() {    std::string input;    std::cout << "Enter the string: ";    std::getline(std::cin, input);    std::string reversedString = reverseOnlyLetters(input);    std::cout << "Reversed string: " << reversedString << std::endl;    return 0; }

Example Input:

cCopy code

Enter the string: a-bC-dEf-ghIj

Example Output:

cCopy code

Reversed string: j-Ih-gfE-dCba

In this code, we use two pointers, left and right, to traverse the string from both ends. We keep incrementing left if the character is not a letter, and decrementing right if the character is not a letter. When both left and right pointers encounter a letter, we swap the characters at those positions. We continue this process until left becomes greater than or equal to right. This ensures that we reverse only the letters while keeping the other characters in their original positions.

The time complexity of this algorithm is O(N), where N is the length of the string. Since we are traversing the string only once, the algorithm is efficient.