After conducting and coaching students through hundreds of interviews, I’ve never EVER seen a case when someone wasn’t asked a string interview question.

Talk about data types that are completely fundamental.

Just like recursion is a critical algorithm for everyone to understand who wants to ace their interviews, strings are really a data structure that you can’t live without.

In this article, I’ll show you everything you need to know to master the string interview.

Here’s what we’ll cover:

1. What is a string, anyway?
2. Java strings, C strings, C++ strings, Python strings, and how to handle all of them
3. The key string interview patterns you need to know to succeed <– Advanced readers start here
4. Common string mistakes that you definitely don’t want to make
5. The 10+ most common string interview questions

Are you ready? Let’s dive in.

What is a String?

Strings are one of the core data types that we use when we’re coding. Every time you want to represent words or text, that’s a string.

That last paragraph was a string. So is this one!

Generally speaking, we’re going to represent a string something like this:

"This is a string. Yay!"

Depending on your programming language, a string can either be a primitive type of an Object, mutable or immutable. But all strings are composed of a sequence of characters.

These characters can be ASCII or Unicode, depending on how we choose to do our encoding.

Essentially all that boils down to is how many characters we have available to us. Since ASCII is only 256 characters, it can be represented by a single byte.

Unicode, on the other hand, is larger and more generalized. We have UTF-8, UTF-16, and even UTF-32, each of which specifies the number of bits per character. That gives us a lot of flexibility (I’m looking at you, emojis).

Since strings are one of the first things that we tend to learn about when learning to program, we won’t spend any more time on general stuff here. Let’s jump right into the meat of what you really need to know.

Java Strings, C Strings, and Python Strings

In this section, we’re going to break down strings by programming language. If there is a specific language that you’re planning on using for your interview, I recommend that you focus there.

Each language differs quite a bit, so let’s get into it!

Java Strings

Fast Facts:

• Mutable? No
• Primitive? No
• Comparison: s1.equals(s2)
• Access the ith character: s1.charAt(i)

When using strings in Java, we need to be aware of several key points that make Java strings unique from strings in other languages.

For starters, strings in Java are actually an Object type and not a primitive. This means that, while we often think of them as a primitive type, strings actually have the properties of Objects more than they do of primitives.

For example, when comparing strings in Java, it is best to use the equals() method rather than ==. This is important because == does not actually compare the value of a string, like it would with a primitive type. Rather, it compares the Object pointers to see if two strings are actually the same object.

equals() is preferred because it will make sure that we are actually comparing the values of two strings, rather than the pointers.

The other thing that we need to be very aware of in Java is that strings are immutable. That means that every time we “modify” a string, we are actually creating a copy.

So what does that mean for us? Well for one, doing something like String s2 = s1 + "z" is not a constant-time operation. Rather it takes time proportional to the length of s1 because we have to copy the entirety of s1 into a new object.

To avoid time complexity issues like this, Java provides us with a StringBuilder class that we will want to use if we are constantly modifying or appending on to a string. A StringBuilder is really a wrapper for an array of characters that provides us with an easy toString() method that we can use to recover a string.

Useful Java String Methods:

• length() – Returns the length of the string
• charAt(int i) – Returns the character at index i
• substring(int i, int j) – Returns the substring from i to j (inclusive of index i and exclusive of index j)
• contains(String s) – Returns a True if s is contained in the string
• indexOf(String s) – Returns the starting index of the first occurrence of s
• toArray() – Converts a string to a character array (useful if we want to repeatedly modify the string)

C Strings

Fast Facts:

• Mutable? Yes
• Primitive? No
• Comparison: strcmp(s1, s2)
• Access the ith character: s1[i]

C is uniquely different from Java in the sense that C strings are nothing more than simple character arrays that are terminated with a null character. This affords us some advantages as well as some disadvantages.

In the pro category, strings in C are mutable. Since it’s just an array it’s easy for us to access any of the characters, modify them, and whatnot. This means that certain types of problems that we might want to do become super easy.

On the flip side, though, it makes a lot of things more difficult. Because strings are not a class of their own, we can’t easily do any operations or comparisons on the strings directly, so we end up having to rely on library functions for basically everything.

Since they are arrays, we also have to allocate the entire size of the string up front or risk having to copy all of the data. We also have to make sure that we are null-terminated or we can run into issues.

Useful C String Functions

• strstr(char *s1, char *s2) – Returns a pointer to the beginning of s1 if found in s2
• strcat(char *s1, char *s2) – Concatenates 2 strings
• strcpy(char *s1, char *s2) – Copies the contents of s1 to s2
• strlen(char *s1) – Returns the length of a string

C++ Strings

Fast Facts:

• Mutable? No
• Primitive? No
• Comparison:s1.compare(s2)
• Access the ith character: s1[i]

Unlike in C, C++ allows the use of std::string which is part of the STL (standard template library). So long as you ensure to #include<string> in your program, you have access to this library and can treat strings in a very similar manner to how they are treated in Java.  

Similar to Java, strings in C++ are treated as objects as opposed to primitives. We see this when we compare two strings by calling s1.compare(s2). However, the standard == operator is overloaded in C++ for std::string to allow for string comparison as well. Convention dictates which of the two are used, but both produce the same result.

Another similarity to Java strings is that C++ strings are immutable. When we alter a string in C++, we are creating a copy of that object. The same pitfalls and caveats we covered for Java strings are applicable here then as well.

Useful C++ String Methods:

• s1.length() – Returns the length of the string (from string::length)
• s1.find(s2) – Returns the index of s1 in the string s2 (from string::find)
• strcpy(char_array, s1.c_str()) – Converts s1 into a character array
• s1.substr(i,j) – Get  the substring of s1 from i with length j

Python Strings

Fast Facts:

• Mutable? No
• Primitive? Yes
• Comparison: s1 == s2
• Access the ith character: s1[i]

In typical Python fashion, this is probably the easiest of these three languages to handle strings. Rather than having to use a lot of function calls, much of what we might want to do is built into the language, such as getting substrings of a string.

However, you should use caution when using Python for one very important reason: The simplicity of the language often masks underlying complexity.

For example, we can very easily get a substring of a string in Python using the Python slicing syntax: s[1:5]. Writing it this way makes it very easy to assume that it is a constant-time operation. However, in most cases, operations like this are still going to copy the substring (remember strings are immutable), meaning that it is going to take us linear time.

Useful Python String Methods:

• len() – Returns the length of the string
• s1 in s2 – Is s1 a substring of s2
• index(s1) – Returns the index of s1 in the string
• list(s1) – Converts s1 into a character array
• s1[i:j] – Get  the substring of s1 from i to j

Don't do another coding interview…​​

…Until you've mastered these 50 questions!

GET YOUR FREE GUIDE

Common String Patterns

When we’re preparing for our interviews, we can approach it a couple of different ways:

1. We can try to memorize as many specific problems as we can in the hopes that we’ll get asked one of those exact questions in our interview.
2. We can learn common patterns that we can apply to many different problems.

I highly recommend that you focus on approach #2 (I talk about this more here). In this section, I’m going to show you the most common string patterns that you are likely to come across so that you can apply them to many different problems.

Using a Length-256 Integer Array

If we wanted to count the occurrences of each character in a string, the obvious approach might be to use some sort of hashtable or dictionary. We could just map the characters to the count of the number of times they occur.

Pretty easy, right?

Except that this really isn’t the best way to do it. A better way would be to use a length-256 array (let’s assume we’re using ASCII) where the index in the array represents the ASCII value of the character and the value at that index represents the count.

Therefore, if we had the string "aaabb", arr[97] = 3 and arr[98] = 2.

Why do this instead of using a hashmap? Simply put, arrays are a much simpler data structure. That means that the computer can manipulate them much faster and you will improve the efficiency of your code.

The one downside of course is that you may be allocating space that you don’t need. A hashmap only allocates space for the characters present in the string. However, this is a small price to pay and the array is a relatively small fixed size, so it is usually worth the cost.

Practice String Interview Questions:

• Anagrams
• Sorting the characters in a string
• Longest substring without a repeating character

Using 2 Pointers

Algorithms that use multiple pointers are super common all over the place. Therefore it’s really good to have a firm grasp of some of the ways this can be helpful.

For starters, we can talk about finding all substrings of a string. Using two pointers and a nested for loop, we can find all the substrings quite easily:

With our two pointers, we simply find every combination of starting point and ending point for our substring. If we wanted to do something with these, we could add them to a list or do any of a million other things.

Another way that we can use two pointers is to reverse a string in place. We will use 2 pointers to find pairs of characters to swap:

Notice two things here. For one, we converted the string into a char array to make it easier for us to swap characters (remember strings are immutable) and we were also able to compute our j pointer from i, rather than having to actually iterate over it separately.

Practice String Interview Questions:

• Remove Duplicates
• Is String a Palindrome
• Reverse Words in a String

String Math

Sometimes we like to convert between strings and integers, refer to characters by their ASCII values, and all sorts of other goodness like that.

We won’t cover the specifics of how to do everything here, since that varies significantly by language, but here are some things that you should know how to do for your chosen language:

• Get the ASCII value of a character
• Convert an ASCII value into a character
• Convert a digit character into its integer value (ie. convert "5" into 5)

You should know the language-specific functions for each of these.

We can also figure out some of these by adding and subtracting different characters from each other. This is afforded because ASCII characters are sequential. Therefore, we can guarantee that '5' - '0' = 5 or 'd' - 'a' = 3.

These sorts of formulas give us a quick and dirty way to figure out things such as what digit a character represents or what number letter a certain letter is in the alphabet.

Exercise: What is some other information you could find out using this strategy?

Another thing that we might want to do is to convert larger numbers into strings or vice versa. To do this we’re going to need to get a little bit more creative. Specifically, we have to be sure to account for the different place values in the number.

For example:

The key thing to notice here is that we have to make sure that we multiply by the correct power of 10. Otherwise we are not going to get the right resulting number.

Practice String Interview Questions:

• Convert Strings to Binary
• String to Integer
• Compare Version Numbers

String Sliding Windows

Sliding windows are a technique that come up a lot when talking about strings and arrays and can be valuable in a lot of different cases. They can make it possible for us to dramatically improve our time complexity in certain cases.

Essentially, sliding windows are a special case of our two pointer pattern that we looked at earlier. We will keep track of a “window” within the string (the range between the two pointers) and only consider the characters within that window at any given time.

What does this allow us to do? Let’s consider the problem of finding the longest substring that doesn’t have any repeated characters.

Obviously our brute force approach could simply be to look at all possible substrings and then check whether they had duplicate characters, but that would take us O(n3) time (we have to iterate over each of n2 different substrings, which takes n time).

But with a sliding window, we can use a greedy approach. Essentially, we will try to move our front pointer forward as far as we can without getting a duplicate character. However, as soon as we find a duplicate character, we can move up our second pointer until it’s no longer duplicated.

Let’s see what this actually looks like:

Essentially what we are doing is continually maintaining the maximum sized window that we can have without containing duplicate characters. This allows us to solve the problem in O(n) time (Note: Even though we have nested for loops, j only goes from 0 to s.length() once).

Practice String Interview Questions:

• Find All Anagrams in a String
• Minimum Window Substring
• Substring with Concatenation of All Words

String Comparison, Alignment, and Matching

We’ve already talked about how you can use 2 pointers in a string to do a variety of different things, from reversing a string to creating a sliding window.

However there’s one more unique application of this basic technique that we need to cover, and that is when we have 2 different strings. By having one pointer in the first string and one pointer in the second string simultaneously, we can do a whole host of different things.

One really common case in which we might use this is to compare two strings. For example, let’s look at how we might determine if one string is a substring of another:

This is a very simple example, but particularly using recursion we can get a lot more advanced. For example, recursion allows us to consider multiple different combinations of pointers to determine which is the best combination, a la finding the longest common substring.

Practice String Interview Questions:

• Longest Common Substring
• Edit Distance
• Regex Matching

Regular Expressions

Regular expressions are a whole beast unto themselves and not something that you need to go into a ton of detail on when you’re preparing for your interviews. However, it does help to at least know the basics and have a general awareness.

The key things that you really need to know here are wildcard matching and repetitions (., *, and + operators). With just these, you will know basically all that you need for your interviews.

When thinking about regular expressions for interviewing, there are two specific aspects that you should keep in mind and be prepared for:

1. How to use built in regular expression matching for your language
2. How to implement basic regular expression matching

#1 is pretty straightforward. Just make sure you know the syntax to build a regular expression and compare it to a string. If you have that down, then you’ll be good.

For #2, I will reiterate the importance of understanding recursion. Doing very basic wildcard matching is easy enough to do iteratively, but as soon as you have an unspecified number of repetitions of a character/string it becomes really hard to do that iteratively.

Recursion essentially allows you to test multiple different paths. It makes it easy for you to test 1 repetition, 2 repetitions, 3 repetitions, and more for any given character without having to explicitly define where the repetitions are. You can sort of imagine it like a nested for loop where the depth of the nesting is defined at runtime.

Practice String Interview Questions:

• Regex Matching
• Wildcard Matching

String Algorithms

The last series of patterns that you should be aware of for your interview is the variety of string-specific algorithms that exist out there. While this is by no means an exhaustive list, it gives you a sense of some things you might want to look at.

Before we get specific, though, I want to caution you. Don’t worry about these until you have everything else dialed in for your interviews. Far too often, I see people focusing on this sort of minutia even though they don’t have some of the most important stuff figured out for their interviews.

If you don’t feel comfortable on all the other major interview topics, don’t come back to this section until you do. It will still be here. And the chances of any of these coming up on your interview is super low. Consider this extra credit.

Finally, a word about how to approach these algorithms.

Don’t worry about memorizing the names and exactly how each algorithm works. There’s basically a zero chance that you’ll actually be asked about that.

The key with these algorithms is to understand the core patterns and concepts that make them work, similar to what we’ve been talking about so far in this post. Focusing on learning the underlying strategy will make these most worth your while.

KMP (Knuth Morris Pratt)

This is a pattern searching algorithm designed to help you more efficiently search for substrings in a larger string. Rather than searching through the entire substring repeatedly, it allows us to optimize to an O(n) time complexity.

Boyer Moore

This is another pattern searching algorithm that enables us to improve our complexity by doing a degree of preprocessing on the substring before performing the search.

Rabin-Karp

This final string searching algorithm uses hashing applied to smaller parts of the string to perform an efficient search.

Common String Mistakes

There are a few common mistakes that I see come up again and again when working with students on string problems, but they all ultimately boil down to one thing:

Strings are not constant size.

We can often become complacent when working with primitive types (or types that feel like primitive types) because we’re used to those types being a constant size. For example, all integers are going to be 32 bits.

This makes it easy when we’re computing any sort of time complexities.

However with strings, it is easy to make similar assumptions (that things will happen in constant time), when in fact, they won’t.

For example, consider this problem a student recently shared with me:

At first glance, the complexity analysis seems obvious enough, right? We have 2 for loops, one after another, each of which goes from 0 to n. Seems simple enough, right?

But look more closely at the second for loop. Is System.out.println(s) really a constant-time operation?

What happens when we call that function. Well for starters, we can’t just print a StringBuilder directly, we actually have to call the toString() method on it. That takes the backing character array and converts it into a string (do I hear an O(n))?

Then once we have a string, we have to actually print the damn thing. Printing isn’t a constant-time operation either. If we think about it at a very fundamental level, to print something on the screen, the data has to be copied into the screen buffer. That takes O(n) time.

All this to say that, while this looks like a super simple example, there’s a lot more going on under the hood than we might initially notice.

So when we work with strings, we want to be extra careful about the time complexity that different operations take. Here are some places we need to be careful:

• Hashing strings. We generally treat inserting and looking up in hash tables to be O(1), which it is, but especially in this case we need to also take into account the amount of time it takes to do the hashing itself
• Modifying strings. Remember that strings are (usually) immutable. That means that any operation that modifies a string, even if it’s as simple as removing the last character, requires us to make a full copy of the string
• General string functions. Like the print() function that we discussed, many seemingly simple function applied to strings can take linear time. Make sure to think critically about what the string functions that you are using are doing under the hood.

Above anything else, the most important thing is to be careful with strings. Often times, we can run into trouble because we assume they behave the same as every other data type we’re used to and they often don’t.

Common String Problems

We’ve now covered all of the core patterns that you need to know to ace any string interview questions. These problems aren’t rocket science but they do come up a lot so it is good to be well prepared.

In this section, I’ve included a selection of problems for you to practice. Practicing problems is incredibly important for ingraining these skills.

But if you don’t practice properly, they won’t be of use to you. I recommend you practice using the following steps:

1. Attempt the problem on your own.
2. If you get stuck, look at the solution and try to understand why you got stuck.
3. Go back and try to solve the problem completely on your own. DO NOT look at the solution.
4. If you get stuck, go back to Step 2.
5. Repeat until you can solve the problem on your own.

With this approach, you ensure that you are really understanding the problem and not just convincing yourself that you know it.

• String Compression
• Anagrams
• Is Palindrome
• String Deletion
• Integer to Roman Numerals
• Longest Common Prefix
• Group Anagrams
• Longest Common Substring
• Permutations of a String
• Autocomplete

Once you’ve mastered these core problems, you can find a large variety of additional practice problems here.

Wrapping Up String Interviews

The key with any interview is not to memorize as many problems and solutions as you can. As tempting as that can be, it will only get you so far.

Rather, true interview mastery comes from deep understanding of the underlying techniques and strategies.

That is what we covered in this post.

Rather than focusing on the specific problems, focus on the patterns that we covered. Make sure you understand how to use strings in your language of choice. Then make sure that you understand not only what the different string patterns are but how you can apply them effectively in your interview.

Do this, and you’ll be way closer to acing your interview!