Day 16 of 75 Day Challenge Leetcode

Leetcode Question Number-: 917. Reverse Only Letters

Question-:

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.

Example -:

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

Solution-:

#include <cctype>
class Solution {
public:
    string reverseOnlyLetters(string s) {
        int i = 0;
        int end = s.size() - 1;
        while (i < end) {
            if (isalpha(s[i]) && isalpha(s[end])) {
                swap(s[i], s[end]);
                i++;
                end--;
            } else {
                if (!isalpha(s[i]))
                    i++;
                else {
                    end--;
                }
            }
        }
        return s;
    }
};

Explanation

Initial State:

• s: "ab-cd"
• i: 0
• end: 4

Iteration 1:

• Check if s[i] ('a') and s[end] ('d') are both alphabetic characters.
• Swap them and increment i and decrement end.
• Resulting s: "db-ca"

Iteration 2:

• Check if s[i] ('b') and s[end] ('c') are both alphabetic characters.
• Swap them and increment i and decrement end.
• Resulting s: "dc-ba"

Iteration 3:

• Check if s[i] ('d') and s[end] ('b') are both alphabetic characters.
• Swap them and increment i and decrement end.
• Resulting s: "db-cd"

Iteration 4:

• i is equal to end, exit the loop.

Final Result:

• The string after reversing only the letters is “db-cd”.

Complexity Analysis:

• Time Complexity: O(N)
• Space Complexity: O(1)