Good afternoon! Here's our prompt for today.
Reversing Only Alphabetical Characters in a String
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:
1'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:
1reverseOnlyAlphabetical('sea!$hells3');You should expect the output to be:
1'sll!$ehaes3'Constraints to Consider
- String Length: The length of the given string is up to
100,000characters. - 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).
Try to solve this here or in Interactive Mode.
How do I practice this challenge?
xxxxxxxxxxvar assert = require('assert');​function reverseOnlyAlphabetical(str) { return str;}​try { assertIsFunction( reverseOnlyAlphabetical, 'reverseOnlyAlphabetical is a function' );​ console.log('PASSED: ' + 'Expect `reverseOnlyAlphabetical` is a function');} catch (err) { console.log(err);}​try { assert.equal( reverseOnlyAlphabetical('sea!$hells3'), 'sll!$ehaes3', "reverseOnlyAlphabetical('sea!$hells3') should equal 'sll!$ehaes3'" );​ console.log( 'PASSED: ' + "Expect `reverseOnlyAlphabetical('sea!$hells3')` to return `'sll!$ehaes3'`" );} catch (err) {Tired of reading? Watch this video explanation!
To change the speed of the video or see it in full screen, click the icons to the right of the progress bar.
Here's our guided, illustrated walk-through.
How do I use this guide?
Choosing a Method: The Art of Reversing
This problem bears a striking resemblance to the classic task of reversing a string or an array. There are numerous methods to achieve this, each with its own pros and cons. My personal favorite for handling a standard string reversal is the Two Pointers with Swap Method.
Imagine your string as a long line of dancers. The two-pointer approach essentially places a dancer at each end of the line. They swap places, and then the dancers take a step inward, again swapping places, until they meet in the middle. It's an elegant and efficient dance, if you will.
xxxxxxxxxxfunction reverseArray(arr) { let start = 0; let end = arr.length - 1;​ while (start <= end) { const temp = arr[start] arr[start] = arr[end]; arr[end] = temp;​ start++; end--; }​ return arr;}The Roadmap to Efficient Reversal and Filtering
The method we're discussing here is a universal tool for efficiently reversing any array or string. It's like the Swiss Army knife of reversals. Once you have a grip on this, the next challenge is merely a process of sifting out the non-alphabetical characters, almost like separating wheat from chaff.
Method 1: Isolate, Store, and Reverse
Step 1: Identify Alphabetical Characters
The first step is to identify only the alphabetical characters in the given string. Think of this as a treasure hunt where you only pick up the gold coins and leave the pebbles behind.
Step 2: Store Them Separately
Once you've identified these "gold coins," you store them in a separate array. Imagine placing the gold coins in a separate bucket.
Step 3: Execute the Reversal
After storing these alphabetic characters, the next action is to reverse them. You can use the two-pointer swap method we discussed earlier for this purpose.
Regex to the Rescue
Regular expressions (regex) can be a helpful tool for identifying the alphabetical characters. You can use a pattern like /[a-zA-Z]/ to spot these alphabetic "gold coins" amidst the string of diverse characters.
By following this method, you can isolate what you need, reverse it efficiently, and leave everything else undisturbed.
1for (let char of str) {
2 if (/[a-zA-Z]/.test(char)) {
3 alphaChars.push(char)
4 }
5}
6
7const reversedAlpha = reverseArray(alphaChars);The Final Act: Swapping Characters Back
Step 4: Initiate a Second Pass
After reversing our isolated "gold coins" (the alphabetical characters), it's time to go through the string again. This second round, starting from the beginning, has a different objective—swapping.
Step 5: Swap Using Position/Index
The plan is simple: replace the alphabetical characters in the original string with the reversed alphabetical characters from our newly created array, reversedAlpha. Think of it like putting the gold coins back but in a new order.
How It Works
Imagine you have two buckets—one with the original gold coins and the other with the gold coins turned upside down (reversed). As you walk along the path where you initially picked the coins, you place the upside-down coins back in their original spots.
By following these steps, we effectively reverse only the alphabetical characters while keeping the non-alphabetical ones intact. It's as if the coins (alphabets) were flipped, while the pebbles (special characters) remained undisturbed.
1for (let i = 0; i < str.length; i++) {
2 if (/[a-zA-Z]/.test(str[i])) {
3 str[i] = reversedAlpha[i];
4 }
5}Navigating the Loop: Advanced Tips
This approach beautifully sidesteps non-alphabetical characters. But let's talk about the "how" for a moment. To ensure accuracy, remember to iterate the reversedAlpha array independently from the loop that scans the original string.
Optional: Simplifying with .shift()
If the thought of juggling another pointer or index leaves you dizzy, here's a simpler alternative: use the .shift() method. This function efficiently grabs the left-most element in an array, essentially doing the pointer's job for you. Imagine it as having a helper who hands you each reversed "gold coin" as you walk along your original path.
Method 2: The Two-Pointer Skip Technique
Dual Pointers with a Twist
The second approach also involves using two pointers, much like our first method. However, this one comes with a twist: it skips over the non-alphabetical characters directly.
How to Skip Efficiently
Just like in a dance, when a couple realizes they are out of sync, they adjust their steps. Similarly, if either of the pointers encounters a non-alphabetical character, it simply "dances" past it, without making a swap.
By adopting this approach, you get to keep the original sequence of non-alphabetical characters intact while reversing only the alphabets. Think of it as flipping some tiles on a mosaic floor without disturbing the overall pattern.
1function isAlpha(c) {
2 return (c >= 65 && c <= 90) || (c >= 97 && c <= 122);
3}
4
5function swap(arr, a, b) {
6 let t = arr[a];
7 arr[a] = arr[b];
8 arr[b] = t;
9}
10
11function reverseOnlyAlphabetical(str) {
12 const result = str.split("");
13 let left = 0;
14 let right = result.length - 1;
15
16 while (left < right) {
17 if (!isAlpha(result[left].charCodeAt())) {
18 left++;
19 } else if (!isAlpha(result[right].charCodeAt())) {
20 right--;
21 } else {
22 swap(result, left++, right--);
23 }
24 }
25
26 return result.join("");
27}
28
29console.log(reverseOnlyAlphabetical("sea!$hells3"));Method 3: Modern Elegance with ES6 and Beyond
Step 1: Extract Only the Alphabets
In this method, we're tapping into the powerful arsenal of ES6 methods, specifically map and filter, to craft a more streamlined solution.
Creating an Alphabetic Array
First off, we extract only the alphabetical characters from the string and store them in a new array, which we'll call alphaOnly.
Here's how you can do it in multiple languages:
1let alphaOnly = str.split('').filter(c => /[a-z]/gi.test(c));Step 2: The Transformation Act
After creating our alphaOnly array, the next phase is where the real magic happens. We'll split the original string into an array and perform a transformation using map.
Returning Non-Alphabetic Characters
During this transformation, if a character does not match our Regular Expression criteria (i.e., it's not an alphabetical character), we simply return it in its current position, leaving it untouched.
Picture this as walking through a garden and only flipping the stones that have a specific marking, while leaving all others in their original state.
xxxxxxxxxxlet alphaOnly = str.split('').filter(c => /[a-z]/gi.test(c)); return str.split('').map( c => { if (/[^a-z]/gi.test(c)) { return c; }});Step 3: The Replacement Dance
Dealing with Matched Characters
When a character matches our Regular Expression (it's an alphabet), we turn to our alphaOnly array. We pull out the last character from this array using splice and use it for the swap. This way, each loop iteration places a unique reversed alphabetical character back into the original string.
Stitching It Back Together
Finally, we use the join('') method to transform our array back into a string, effectively reversing only the alphabetical characters while leaving all others intact.
Complexity of the Final Solution
Time Complexity
Our final solution maintains a time complexity of O(n), where n is the total number of characters in the input string. Each loop iteration, as well as the filter and map functions, work in linear time, keeping the process efficient.
Space Complexity
The space complexity also stands at O(n) because we use an auxiliary array (alphaOnly) to temporarily store the alphabetical characters.
xxxxxxxxxxlet alphaOnly = str.split('').filter(c => /[a-z]/gi.test(c)); return str.split('').map( c => { if (/[^a-z]/gi.test(c)) { return c; }​ let next = alphaOnly[alphaOnly.length - 1];​ alphaOnly.splice(alphaOnly.length - 1, 1);​ return next;}).join('');One Pager Cheat Sheet
- You can
reverseOnlyAlphabeticalcharacters in a given string withlength <= 100000and composed of ASCII characters inO(n)time and space complexity. - The
two pointers with swapmethod is recommended to reverse a regular string. - We can
reverseArraythe alphabetical characters of a string using/[a-zA-Z]/in aforloop to efficiently reverse only the alphabetical characters. - We can swap out alphabetical characters in the string with
elements from our newly created reversedAlphabased on the position/index. - Using the
.mapand.filtermethods, one can reverse only alphabetical characters in a more succinct manner. - We
splitthe string into anarrayand loop over it withmapto return non-alphanumeric characters in their current positions. - We
spliceandjoinour array to remove unmatched characters and turn it back into a string, resulting in anO(n)time and space complexity.
This is our final solution.
To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.
xxxxxxxxxx}var assert = require('assert');​function reverseOnlyAlphabetical(str) { const alphaChars = []; str = str.split(''); // strings are immutable in JS​ for (let char of str) { if (/[a-zA-Z]/.test(char)) { alphaChars.push(char); } }​ const reversedAlpha = reverseArray(alphaChars);​ let idxRA = 0; for (let i = 0; i < str.length; i++) { if (/[a-zA-Z]/.test(str[i])) { str[i] = reversedAlpha[idxRA++]; } }​ return str.join('');}​function reverseArray(arr) { let start = 0; let end = arr.length - 1;​ while (start <= end) { const temp = arr[start]; arr[start] = arr[end]; arr[end] = temp;Alright, well done! Try another walk-through.
If you had any problems with this tutorial, check out the main forum thread here.