Strings

Strings are very common in the interview questions. In this section, we will cover some common string manipulation techniques, and solve some typical problems.

String concatenation

What do you think is the time complexity of the following code in Java?

final int N = ...

String s = "";        
for (int i = 0; i < N; i++)
    s = s + "x";

It can be a bit surprising, but this code actually runs in O(N²) time. The reason is that in Java strings are immutable, and as a result, each time you append to the string new string object is created. The loop in the code does 1 + 2 + 3 + ... + N = N * (N + 1) / 2 = O(N²) operations.

To avoid this, in Java you should use StringBuilder class. The following code runs in O(N) time:

final int N = ...

StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++)
    sb.append("x");

String s = sb.toString();

In C++, strings are mutable, but you still should be careful with concatenation. As a rule of thumb, you should use += operator or append method (they append to the original string object), and avoid + operator (it creates a new string object):

const int N = 300000;

// this code works 14.52 seconds on my machine
string s = "";
for (int i = 0; i < N; i++)
    s = s + "x";

// this one – 0.02 seconds
string s = "";
for (int i = 0; i < N; i++)
    s += "x";

// this one – 0.02 seconds as well
string s = "";
for (int i = 0; i < N; i++)
    s.append("x");

Parsing

In a lot of string problems, you need to parse something. To simplify the task, it's a good idea to learn built-in string functions in your language of choice. Some of the most useful functions are splitting by separator, taking a substring of a string, converting between lower and upper case, and checking if the character is digit or letter – look these up in your language!

Let's consider an example problem:

After you are comfortable with built-in string functions, now it may actually be a good idea to try to solve some problems without them. How would you implement them yourself?

Let's practice on another problem:

Often, parsing can become quite complicated. You should carefully check your current code state, think what you are looking for next, and try to handle all edge cases. Try to solve the following classic problem:

Building a string

In the following problem you need to construct a required string yourself. It's a great way to practice to handle all the different edge cases. Can you solve it?

More practice problems

Here are some more good string problems you can practice on: