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.
// 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
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.
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.
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:
start
and end
pointers to the beginning and end of the string, respectively.
start
pointer to the right until we find a consonant.
end
pointer to the left until we find a consonant.
start
and end
once both pointers are pointing to consonant characters.
start
by 1 and decrement end
by 1, so that we don't swap the same pair again.
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.
Since we are making only one pass through the string, the time complexity is O(N)
.
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.
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("");
}