Community

Start a Thread
Filters
By Category
Notifications
Subscribe You’re not receiving notifications from this thread.

Reverse Only Alphabetical (Main Thread)

Here is the interview question prompt, presented for reference.

Reversing Only Alphabetical Characters in a String

![Visual Diagram](https://storage.googleapis.com/algodailyrandomassets/curriculum/easy-strings/reverse-only-alphabetical.png)

The Problem Statement

You are provided with a string that's a blend of alphabetic and non-alphabetic characters. Think of a beach where you find both shells (a-Z) and other things like plastic wrappers or dollar bills ($, !, etc.). For example, you might get:

'sea!$hells3'

Your mission, should you choose to accept it, is to flip only the alphabetical shells while keeping the other items ($, !, etc.) in their original positions.

For example, when calling:

reverseOnlyAlphabetical('sea!$hells3');

You should expect the output to be:

'sll!$ehaes3'

Constraints to Consider

  • String Length: The length of the given string is up to 100,000 characters.
  • Character Set: You'll be working with ASCII characters.
  • Time Complexity: Aim for a time complexity of O(n).
  • Space Complexity: Aim for a space complexity of O(n).

You can see the full challenge with visuals at this link.

Challenges • Asked about 6 years ago by Jake from AlgoDaily

Jake from AlgoDaily Commented on Jul 09, 2019:

This is the main discussion thread generated for Reverse Only Alphabetical.

Jake from AlgoDaily Commented on Jul 09, 2019:

Hi @mattvanwinkle:disqus - thanks so much for catching this. I've updated the test cases to be correct.

For those reading-- in the original solution, in the second for-loop, I was not using a separator index to track the elements in reversedAlpha. Hence, the letters were incorrectly placed. My bad!

John Commented on Jul 13, 2019:

I was a bit stumped by this one - shouldn't the the reversedAlpha array would have less indices than the original string if the original string contained characters?i.e. - input string - 'h!ey'reversedAlpha = ['y', 'e', 'h'];so on the 4th iteration over this string wouldn't it return undefined for the character to swap?

update - ahh, I see! the solution you use has a separate index for that (as mentioned in your comment)

Anonymous Commented on Feb 12, 2020:

Hi, I'm using Python but it seems one can use the 2 pointer technique (as mentioned) for this problem. So the algorithm would be something like:

  1. Create a pointer at the beginning (i)
  2. Create a pointer at the end (j)
  3. Check if i and j are alphabetical characters
  4. If they are then swap
  5. If they're not then don't swap and either increment i or decrement j

This way you don't have to use a regular expression, but I'm not sure of the time complexity? O(N)?

Anonymous Commented on Sep 17, 2020:

╷
├─ JUnit Jupiter ✔
└─ JUnit Vintage ✔
└─ MainTest ✔
├─ firstTest ✘ expected:<[[s, l, l, !, $, e, h, a, e, s, 3]]> but was:<[sll!$ehaes3]>
└─ secondTest ✘ expected:<[[1, a, d, j, 9, 0, s, a, k, 3]]> but was:<[1adj90sak3]>

Isn't the function supposed to return a single string? The characters are in the correct order but the tests fail due to difference in representation.. (I am returning a String as it is set by default return type).

Oliver Price Commented on Jun 05, 2022:

I think using regex slows down this solution quite a lot.

I use the double-pointer method on the original string, only swapping if they are both alpha, and otherwise just incrementing/decrementing the index that is non-alpha.

For the 3rd test case this is about 13x faster than the main solution:

SNIPPET
def reverse_alphabet_only(s):
    output_str = list(s)
    start = 0
    end = len(s) - 1
    for i in range(len(s)):
        char1 = s[start]
        char2 = s[end]
        if char1.isalpha() and char2.isalpha():
            output_str[start] = char2
            output_str[end] = char1
            end -= 1
            start += 1
        elif char1.isalpha() and not char2.isalpha():
            end -= 1
        elif char2.isalpha() and not char1.isalpha():
            start += 1
        else:
            end -= 1
            start +=1

        if end <= start:
            return "".join(output_str)