Practice: Reverse Consonants

In this assignment, we'll again apply the techniques learned so far by solving the "Reverse Consonants" problem. Try to solve the problem using the naive (brute-force) approach first, and then see if you can optimize the solution.

Problem Description

// Given a string `str`, reverse only all the consonants in the string and return it.
// Consonants are all alphabetic characters except for the vowels `'a'`, `'e'`, `'i'`,
// `'o'`, and `'u'`, which can appear in both lower and upper cases.
// The consonants can appear more than once in the string.

console.log(reverseConsonants("") === "");
console.log(reverseConsonants("s") === "s");
console.log(reverseConsonants("HELLO") === "LELHO");
console.log(reverseConsonants("leetcode") === "deectole");
console.log(reverseConsonants("example") === "elapmxe");
console.log(reverseConsonants("Consonants") === "sotnonasnC");

// All test cases should log true

Walkthrough & Solution

Use start-end pointer strategy.

The easiest way to find consonants is to create a string with all consonants and check whether the character is included in that string.

High Level

For this solution, we'll use the start-end pointer strategy. Our start pointer will move to towards the end of the string looking for consonants while our end pointer will move towards the beginning looking for consonants. Once each pointer has found a consonant, we'll swap those characters. Once start and end meet, we know we've processed the whole string.

Algorithm

We can define a helper function to check whether a character is a consonant. The toLowerCase() string method will be helpful for making this case-insensitive.

In the main function, we can follow these steps:

  1. Split the string into an array of characters.
  2. initialize start and end pointers to the beginning and end of the string, respectively.
  3. Move the start pointer to the right until we find a consonant.
  4. Move the end pointer to the left until we find a consonant.
  5. Swap the characters at start and end once both pointers are pointing to consonant characters.
  6. Increment start by 1 and decrement end by 1, so that we don't swap the same pair again.
  7. Repeat steps 3-6 until the start pointer becomes either equal to or greater than the end pointer. Once that happens, the reversal process is completed, and we can join the array and return the reversed string.

Time Complexity

Since we are making only one pass through the string, the time complexity is O(N).

Space Complexity

We are not using any additional space to solve the problem, which means that the auxiliary space complexity is constant, or O(1). Note that we are talking about auxiliary space complexity here, as we are not accounting for splitting the string into an array of characters. This is because strings are immutable in JavaScript, and we wouldn't be able to mutate them in any solution.


Walkthrough

Let's go through the example string HELLO step by step.

Step 1: In the first step we are splitting the string into an array of characters and initializing two pointers start (s) at index 0, and end (e) at index 4.

Step 2: In the second step, we move the start pointer (s) until it reaches a consonant character. Since it is already pointing at a consonant, 'H', it remains where it is.

Step 3: Next, we move the end pointer (e) until it reaches a consonant character. We only have to decrement once and we reach 'L'.

Step 4: Now, when both pointers point to consonants, we swap those consonants.

Step 5: After swapping, we increment the start pointer by 1 and decrement the end pointer by 1.

Step 6: We repeat the process. First, we move the start pointer (s) until it reaches a consonant character. We increment it once to reach 'L'.

Step 7: Next, we would move the end pointer (e) until it reaches a consonant character. It's already pointing to 'L', so we leave it where it is.

Step 8: In the final step, both pointers point to consonants. However, since start and end pointers are equal, this means we are done with the reversal process, and we can join the array back into the string and return the reversed string.

const isConsonant = (char) => {
  return "bcdfghjklmnpqrstvwxyz".includes(char.toLowerCase());
};

function reverseConsonants(str) {
  let chars = str.split("");
  let s = 0;
  let e = str.length - 1;

  while (s < e) {
    if (!isConsonant(chars[s])) {
      s++;
      continue;
    }
    if (!isConsonant(chars[e])) {
      e--;
      continue;
    }
    [chars[s], chars[e]] = [chars[e], chars[s]];
    s++;
    e--;
  }

  return chars.join("");
}