The Technical Interview Guide to String Manipulation

JavaScript string manipulation for interview prep and daily coding

A string is a sequence of characters. It is either a constant or a variable. It is an essential data type in a programming language. In this article, we focus on JavaScript string manipulation. However, the principle and algorithms can be applied to other languages as well.

When you are presented with a technical interview, the interviewer is looking for a few things:

How good is your programming skill?
How up-to-date is your language skill?
How good is your problem-solving skill?

This interview series prepares you for a successful technical interview, but it is also useful for daily coding.

In the code gist format, we list important features of a JavaScript string, which is the foundation of programming skill. There are properties and methods that have existed for 20 years, as well as features in ES2021. You may already know all of them. If there is anything unclear, you know where you need to study some more.

Empowered with JavaScript programming language, we can solve a number of word problems. These algorithms, or their variations, are frequently tested in a real interview.

String Properties and Methods

A string is used to represent and manipulate a sequence of characters. There are a number of string properties and methods. The following are code samples for review, including matchAll in ES2020, replaceAll in ES2021, and at in ES2022.

Map and Set

For string manipulation, we need to store intermediate values somewhere. Array, Map, and Set are popular data structures that you need to master. We will discuss Array in another article. Here, Set and Map are reviewed.

Set

Set is an object to store unique values of any type. The following are code samples for review. It should be self-explanatory.

Map

Map is an object to hold key-value pairs. Any value may be used as either a key or a value. A Map remembers the original insertion order of the keys. The following are code samples for review. It should also be self-explanatory.

Word Problems

There are many English word problems in an interview. We explore some algorithms that are frequently tested.

Isogram

An isogram is a word in which no letter of the alphabet occurs more than once.

The following are long isograms:

dermatoglyphics (15 letters)
hydropneumatics (15 letters)
misconjugatedly (15 letters)
uncopyrightable (15 letters)
uncopyrightables (16 letters)
subdermatoglyphic (17 letters)

How do you write an algorithm to detect whether a string is an isogram? There are many ways to accomplish it. We can put the string in a Set, and then it is automatically split into characters. Since Set is an object to store unique values, its size should be the same as the string length if it is an isogram.

The algorithm’s time complexity is O(1), and space complexity is O(1).

The following are verifying tests:

Pangram

A pangram is a sentence that contains all 26 letters of the alphabet, regardless of case. Ideally, the sentence is as short as possible.

The following short sentences are pangrams:

Waltz, bad nymph, for quick jigs vex. (28 letters)
Jived fox nymph grabs quick waltz. (28 letters)
Glib jocks quiz nymph to vex dwarf. (28 letters)
Sphinx of black quartz, judge my vow. (29 letters)
How vexingly quick daft zebras jump! (30 letters)
The five boxing wizards jump quickly. (31 letters)
Jackdaws love my big sphinx of quartz. (31 letters)
Pack my box with five dozen liquor jugs. (32 letters)
The quick brown fox jumps over a lazy dog. (33 letters)

There are also many ways to verify whether a given string is a pangram. This time, we put each letter (convert to lower case) into a Map. If the Map has the size of 26, it is a pangram.

The algorithm’s time complexity is O(n), and space complexity is O(1).

The following are verifying tests:

Isomorphic strings

Given two strings s and t, they are isomorphic if the characters in s can be replaced to get t. Any character conversion in s must be applied to all the same characters in s. For example, murmur is isomorphic to tartar, if m is replaced by t, u is replaced by a, and r is replaced by itself.

The following algorithm uses an array to store the conversion characters. It will work with a Map, too.

The algorithm’s time complexity is O(n), and space complexity is O(1).

The following are verifying tests:

Anagram

An anagram is a word that is formed by rearranging the letters of a different word, typically using all the original letters exactly once.

There may be many possibilities to rearrange the word from a pool. For example, cat has the anagrams cat, act, atc, tca, atc, and tac. We can add an additional requirement that the new word must appear in the source string. If the source is actually, the resulting array is ["act"].

The algorithm’s time complexity is O(n), and space complexity is O(1).

The following are verifying tests:

Palindrome

A palindrome is a word or sentence that reads the same forward and backward. There are a lot of palindromes, such as A, Bob, and “A man, a plan, a canal — Panama.”

All algorithms to check a palindrome are divided into two types. One uses a loop to check from both ends whether they are the same, and the other one uses recursion to check from both ends whether they are the same. The following code uses the recursion method.

The algorithm’s time complexity is O(log n), and space complexity is O(log n). If we use indexes to make the substring, instead of using s.slice, the space complexity can be O(1).

The following are verifying tests:

There are many palindrome interview questions with some variations. The following is an algorithm to find the longest palindrome in a given string.

The algorithm’s time complexity is O(nlog n), and space complexity is O(1). The following are verifying tests:

Conclusion

There are other word problems. Practice makes perfect.

The following are other interview guides:

Thanks for reading.

Want to Connect?

If you are interested, check out my directory of web development articles.