String Questions in Interviews

String questions are often some of the more straightforward interview questions out there. After all, which computer science student hasn’t been subject to endless assignments requiring string manipulation? (Remember all those reverseString recursion problem sets?)

Still, string questions can be tricky, and designing and implementing an efficient approach, while being scrutinized, is no easy feat. Here is a guide, compiled from various books, articles and friends, to help you defeat the dreaded string interview question.

A Brief Summary

First off, remember that Strings are in fact, at a lower abstraction level, arrays of Characters. Java and C programmers will be acutely aware of this. Higher-level languages, such as Python or Javascript, tend to hide such details. No matter your language of choice, keep the structure of Strings in mind when tackling String problems.

This means that String and Array questions share similar approaches. For example, sorting according to a certain key, or finding the difference between the biggest and smallest element in a list. String questions are instead mostly limited to permutations of the existing data within the Character array. There are 5 fairly common types of String questions:

  1. Generate all permutations of a given String
  2. Substrings of a given String
  3. Reversing a given String
  4. Substitution/Replacing specific letters
  5. String Compression

Remember the StringBuffer

Before we begin analyzing each problem, there is one String attribute often overlooked: Strings are immutable.

A common practice is to create a String accum variable and update it with every iteration of the loop. For example, this function that reverses a String.

public static String reverseWrong(String x) {
  // convert x into an array
  char[] string = x.toCharArray();
  // create variable to hold answer
  String ans = "";
  // iterate from the back of the array, each time adding a character to ans
  for (int i = string.length - 1; i >= 0; i--) {
    ans += string[i];
  }
  // return as a String
  return ans;
}

Figure 1: Java sample function

Strings’ immutability means that the String variable `ans` is actually destroyed and re-created every time a new character is added to it. Each time a new String is created for `ans`, Java allocates a new array of size `x + 1`, where `x` is the number of characters in the existing String. Java then copies the existing `x` character over and inserts the new character into the last slot. If `n` is the size of the given String, the loop means this happens `n` times. Thus, the total time spent computing ans is `O(1 + 2 + 3 + … + n)`. By summation, this reduces to `n(n+1)/2` or `O(n^2)`. No matter how efficient the algorithm, the function has at best quadratic runtime – terrible.

 

The solution is to use a `StringBuffer`. This is an array pre-allocated with spare memory, with additional characters inserting into the array itself. Dynamic arrays can also be used, if sizes are not known beforehand. The final String is only created once all String manipulation operations have concluded. With only one pass through the characters, total time drops to `O(n)` – linear.

Java has kindly provided the helpful `StringBuffer` class for this. Unlike `Strings`, the `StringBuffer` class is mutable, eliminating our quadratic runtime problem. Figure 2 demonstrates the optimal way of String manipulation in Java, note the use of `StringBuffer`.

public static String reverseCorrect(String x) {
  // convert x into an arrayj
  char[] string = x.toCharArray();
  // create the StringBuffer object
  StringBuffer buffer = new StringBuffer();
// iterate from the back of the array, each time adding a character to buffer
  for(int i = string.length - 1; i >= 0; i--) {
    buffer.append(string[i]);
  }
  return buffer.toString();
}

Figure 2: Java StringBuffer example

Since Python does not possess a dedicated StringBuffer data structure. Python programmers often use a list. New characters are added to the list, and the final String is created by joining all elements in the list

As long as you follow the StringBuffer’s basic concept, it is not necessary to strictly adhere to these implementations during your interview. If the precise syntax is fuzzy, feel free to create your own.

Note that not all interviewers will fuss over this, and that this does not apply to all questions. But it never hurts to know.

String Question Type 1 – Generate all permutations of a given String

This is one of the most common interview questions given, and will be good to know by heart. Because your first instinct is to look for an elegant algorithm (which is a good habit), the question may initially seem daunting. The trick here is to realize that generating all permutations of a given String of size n always results in a O(n!) time, both iteratively and recursively.

Consider the string “abc”. The first character ‘a’ can be placed in 3 slots – first, second and third. ‘b’ can be placed in only 2 slots, since one slot is already taken by ‘a’. ‘c’ has no choice but to go into the remaining slot. Hence the total permutations are 3 x 2 x 1 = 6 = 3!. Correspondingly, there are 6 permutations: “abc”, “acb”, “bac”, “bca”, “cab” and “cba”.

We implement a recursive solution as it is more elegant and thus easier to understand (Figure 4).

public static void permutate(String str) {
  permutation("", str);
}
  
private static void permutation(String ans, String remain) {
  int n = remain.length();
  // ans serves as an accumulator variable
  // base case: we print out ans since there are no more letters to be added
  if (n == 0) {
    System.out.println(ans);
  }
  // recursive case
  else {
    for (int i = 0; i < n; i++) {
      // we call permutation, each time combining prefix with the individual letters in str
      // we also remove these letters from str
      permutation(ans + remain.charAt(i), remain.substring(0,i) + remain.substring(i+1, n));
    }
  }
}

Figure 4. Java Recursive String Permutation function

 

Note that since the runtime is factorial, StringBuffer is redundant here.

I do not recommend testing this code with an input size longer than 15 characters, not because it isn’t efficient, but because there are simply too many possibilities. Feel free to also implement an iterative version!

Question Type 2 – Substrings of a given String

There are several questions that fall into this category.

First, check if a two strings are substrings of each other.

This is a relatively simple one. Refrain from reinventing the wheel by utilizing Java’s indexOf or contains method for Strings and Python’s “in” keyword. Hey Presto! Solved in three lines!

However, this is often an easy lead up to String rotations and the next question will likely be: “Now check if one string is a rotation of another.

For example, “forinterviewscoding”, “interviewscodingfor” and “dingforinterviewsco” are all valid rotations of the string “codingforinterviews”, while “codngiforinterviews” is not.

The key to this is observing that the original string is a substring of the rotated string added to itself.

Consider, the original string “codingforinterviews” and the rotated string “dingforinterviewsco”.

Let, x = “codingforinterviews” and y = “dingforinterviews”

Further, let “codingforinterviews” be broken up into 2 substrings, a and b.

Hence x = ab.

Let a = “co” and b = “dingforinterviews”.

Thus y =“dingforinterviewsco” = ba,

and y + y = baba = “dingforinterviewscodingforinterviewsco”.

Therefore, if y is a substring of x, x will always be a substring of (y + y)

Similarly, the code for this is straightforward (Figure 5).

// it is better practice to separate functions
public static boolean isSubstring (String a, String b) {
  // we first check the length of the strings 
  if (a.length() < b.length()) {
    return b.contains(a);
  }
  // feel free to use indexOf
  return a.contains(b);
}
  
// assuming that a is the rotated string
public static boolean isRotation (String a, String b) {
  if (a.length() != b.length()) {
    return false;
  }
  return isSubstring(a+a,b);
}
  
// the entire function can be optimized to this
public static boolean isRotation2 (String a, String b) {
  return (a.length() == b.length() && isSubstring(a+a,b));
}

Figure 5. Java String Rotation function

Comparing the lengths of the two strings takes O(n), where n is the length of the longer string, while Java’s contains method operates in O(n), bringing the function’s runtime to a very efficient O(n), with no additional space needed.

Lastly, we tackle the problem:

String Question Type 3 – Determine if one string is a permutation of another

The brute-force method, and simplest, is to compute and store all possible string permutations in an array, and iterate through, checking. However, as discussed above, this results in an terrific O(n!) time – unacceptable.

Instead, the optimal approach here is to realize that considering specific ordering adds an unnecessary layer of complexity since all permutations of a given string have the same number of characters as the original string. We can solve this problem by counting characters (Figure 5).

public static boolean isPermutation (String a, String b) {
  // first check if both strings are the same length
  if (a.length() != b.length()) {
    return false;
  }
  // change a to char array to be iterated through
  char[] astr = a.toCharArray();
  // initialize an array as a counter
  int[] count = new int[128];
  // then we count a's characters
  for (char character : astr) {
    count[character]++;
  }
  // match a's count with b
  char[] bstr = b.toCharArray();
  for (char character : bstr) {
    if(--count[character] < 0) {
      return false;
    }
  }
  return true;
}

Figure 5. Java String Permutation function

Comparing length and counting operations both take O(n), since both are completed in one pass. Hence overall time is a nifty O(n), with O(n) extra space utilized for the arrays.

Another acceptable approach is to sort both strings, comparing each entry of the sorted strings. Since all permutations have the same number of characters, the sorted strings must be identical. Sorting, however, is dependent on input sequence, and adds another layer of complexity to the code. Counting characters is simple and direct.

String Question Type 4 – Reversing Strings

String reversal questions are also common. Similar to substrings, such questions often consist of 2 parts, reversing a given string, and then reversing words within a given sentence.

Let’s start with reversing a given string.

This is as simple as string questions can get. Such questions are commonly known as “filibusters”, and are intended to weed out the 95% of candidates who strangely, for some reason, are unable to write viable code. There are no hidden tricks or fancy algorithms, with the exception of StringBuffer. Figure 2 provides the iterative version with StringBuffer integrated.

Because we do this in one pass, the time taken is O(n) with additional O(n) space for the array.

Now, using the above function, reverse the words in a string. For example, “coding for interviews” is reversed to “interviews for coding”.

The trick here is to notice that reversing the entire sentence immediately reverses the sequence of words, though the words themselves are jumbled. “coding for interviews” turns into “sweivretni rof gnidoc”. We then reverse each individual word back to its correct orientation, generating “interviews for coding” (Figure 6).

public static String reverseSentence (String x) {
  // first reverse the string x using the previous function
  x = reverseCorrect(x);
  // split x, effectively extracting the individual words
  String[] words = x.split(" ");
  // create a StringBuffer
  StringBuffer buffer = new StringBuffer();
  // reverse and add the entries in words to buffer
  for (int i = 0; i < words.length; i++) {
    System.out.println(words[i]);
    buffer.append(reverseCorrect(words[i]) + " ");
  }
  return buffer.toString();
}

Figure 6. Java Reverse Sentence function

The reversal function is a constant O(n) since it only requires one pass. Splitting and appending both take O(n), as they too complete their tasks in one pass. Hence the overall function completes in O(n) time, with O(n) additional space for word extraction. This is also a fantastic example of StringBuffer’s practicality. Without a buffer, the overall time would have at least been an absymal O(n^2) no matter the algorithm.

Note that there are shorter ways to solve the question if the interviewer goes straight to reversing words in a sentence. As Figure 7 demonstrates, Java has excellent inbuilt libraries for this task.

public static String reverseSentenceQuick (String x) {
  // use the split method
  String[] words = x.split(" ");
  // create a StringBuffer	
  StringBuffer buffer = new StringBuffer();
  // we append starting from the end of words
  for(int i = words.length - 1; i >= 0 ; i--)
  {
     buffer.append(words[i]);
  }
  return buffer.toString();
}

Figure 7: Java Reverse Sentence Library Implementation function

Because some interviewers frown on using certain built-in methods, it is beneficial to know both approaches and confirm with your interviewer a certain appproach is OK.

String Question Type 5 – Replacements and Deletions

Common and easy to implement, String replacement/deletion are also common filibuster questions, especially for the initial phone screens before the actual on-site interviews. Getting a good grasp of them doesn’t necessary set you apart, but primes the interviewer to expect more from you, which is always good.

First, we tackle: Write a method to replace all whitespaces in a string with #20.

I am sure you recognise a pattern by now: our algorithm should finish its task within one pass of the string for optimal efficiency. This means that iterating through the String and replacing whitespaces with #20, though straightforward, is perhaps the best and simplest approach. As always, the devil is in the details.

 

Most programmers get caught up in their excitement and tap out the following function (Figure 8).

public static String replaceWrong (String x) {
  char[] word = x.toCharArray();
  // iterate through x, replacing whitespace
  for (int i = 0; i < x.length(); i++) {
    if (word[i] == ' ') {
       word[i] = 'a'; // <---- issue here
    }
  }
  return new String(word);
}

Figure 8. Buggy Java String Replacement function

This function will not work as it is does not account for the additional whitespace the inserted characters will take up. Forestall any embarrassment by remember to first count the whitespaces, ensuring your array contains enough spaces. It is also wise to demonstrate initiative to the interviewer by removing any hard-coded values. The resultant function should look something like this.

public static String replaceCorr (String x, String replace) {
  // count the number of whitespace to be replaced
  int count = 0;
  for (int i = 0; i < x.length(); i++) {
    if (x.charAt(i) == ' ') {
      count++;
    }
  }
  // create an array, including the whitespace
  char[] word = new char[x.length() + count * replace.length() - 1];
  int index = 0;
  //iterate through x, replacing whitespace
  for (int i = 0; i < x.length(); i++) {
    if (x.charAt(i) == ' ') {
      for (int j = 0; j < replace.length(); j++) {
        word[index++] = replace.charAt(j);
      }
    }
    else {
      word[index++] = x.charAt(i);
    }
  }
  return new String(word);
}

Figure 9. Correct Java String Replace function

The time taken is O(m), where m is the length of the original string including the additional characters. As this is achieved in one pass, it is optimal.

There is however, further possible optimization. Remember StringBuffer? This is where your knowledge of such a function will make you shine. Proper usage of StringBuffer here further shortens the code (Figure 10).

public static String replaceCorrBuff (String x, String replace) {
  // create a StringBuffer
  StringBuffer buffer = new StringBuffer();
  // iterate through x, replacing whitespace
  for (int i = 0; i < x.length(); i++) {
    if (x.charAt(i) == ' ') {
      buffer.append(replace);
    }
    else {
      buffer.append(x.charAt(i));
    }
  }
  return buffer.toString();
}

Figure 10. Java String Replace function using StringBuffer

Though improvement in performance is marginal, and this is a filibuster question, it is always good to demonstrate an ability to improve and optimize.

Here the #20 is a mere placeholder, and your interviewer might well use other characters, or throw in multiple replacements. This approach should apply, nonetheless.

Not surprising, deletion is a much easier, since there are no additional spaces to account for. As with replacements, and String questions in general, we go through the list, deleting the specified characters. Use StringBuffer whenever appropriate.

String Question Type 6 – String Compression

Though less frequent, String Compression questions do pop up a significant portion of the time. Though phrased differently, the questions are often variations of string compression through character counts. For example, compressing the string “aaabbbcccc” to “a3b3c4”.

Here, the naive approach – iterating through the string, counting characters as they appear – is somewhat correct. As above, the crux lies in using a StringBuffer. Without doing so, the runtime will be O(n + q^2), where n is the length of the original string and q is the number of character sequences. With a StringBuffer, runtime is now O(n + q), since string concatenation is limited to only the character sequences, and no longer quadratic (Figure 1).

public static String compressString(String x) {
  // create a buffer
  StringBuffer buffer = new StringBuffer();
  // to hold the current alphabet
  char current = x.charAt(0);
  // to hold the current count
  int count = 1;
  // iterate through the array, counting
  for (int i = 1; i < x.length(); i++) {
  // update buffer if the letter has changed
    if (current != x.charAt(i)) {
      buffer.append(current);
      buffer.append(count);
      current = x.charAt(i);
      count = 1;
      }
    else {
      // increment the counter
      count++;
    }
  }
  // remember to add the last character
  buffer.append(current);
  buffer.append(count);
  // return a string
  return buffer.toString();
}

Figure 11. String Question Solution: Java String Compression with StringBuffer

There is however, one logical error. If we were doing this by hand, we would only compress the string if its compressed version is shorter than the original. Else, we return the original string. Figure 12 shows the final solution.

public static int countCompress(String x) {
  // total size of string
  int size = 0;
  // count for each char
  int count = 1;
  char current = x.charAt(0);
  // iterate through, counting
  for (int i = 1; i < x.length(); i++) {
    // update if current character is different
    if (current != x.charAt(i)) {
      current = x.charAt(i);
      // we add the length of the char and its count
      size += 1 + String.valueOf(count).length();
      count = 1;
    }
    // increment count if similar
    else {
      count++;
    }
  }
  // we update size to include the last char
  size += 1 + String.valueOf(count).length();
  return size;
}

public static String compressString(String x) {
  // first use countCompress
  int length = countCompress(x);
  if (length > x.length()) {
    return x;
  }
  // create a buffer
  StringBuffer buffer = new StringBuffer();
  // to hold the current alphabet
  char current = x.charAt(0);
  // to hold the current count
  int count = 1;
  // iterate through the array, counting
  for (int i = 1; i < x.length(); i++) {
  // update buffer if the letter has changed
    if (current != x.charAt(i)) {
      buffer.append(current);
      buffer.append(count);
      current = x.charAt(i);
      count = 1;
    } else {
      // increment the counter
      count++;
    }
  }
  // remember to add the last character
  buffer.append(current);
  buffer.append(count);
  return buffer.toString();
}

Figure 12. Full Java String Question solution for String Compression.

Though somewhat long, if you made it this far and your interviewer is able to push you to this point during the session, bonus points for being comprehensive and robust!

Onward to String Question Mastery!

String questions are not necessarily easy, and not necessarily difficult — they come in all shapes and sizes. Interviews can be nasty, stressful and nerve-wrecking affairs, and you’ll want to go in there as confident as you can be. Spread your preparation out and make sure to tackle the most important topics. Don’t hyper-focus on BSTs, for example, but then completely gloss over string manipulation. Yes, this can happen!

String questions you get will typically be variants of those listed above. Be flexible. Perhaps the input you need to compress is jumbled? In that case, sort before doing anything. Or maybe what needs replacing is not whitespace but an entire substring?

In any case, these approaches should still apply. Remember, Strings often require iteration, and the key is to limit this to just one pass. Oh yes and StringBuffer is, almost always, a must.

Good luck!

Posted in Preparation, Strings
  • Kriis

    Any plans on further posts like this? After working through the problems at the end of chapter 1, I saw this and hoped there would be more posts for further chapters. What will I read when I finish with chapter 2-Linked Lists?

  • I must say, good questions and the way you have explained is great, I really like learning from mistake approach. Btw, I have also shared some basic coding questions, your readers may like.

  • Joe Porter

    love the string questions Shaaz! I think there’s a really good
    Live coding interview question example that people would enjoy since so many interviews are just done through online tools nowadays!

  • Kutay Kalkan

    Question 3 ‘s solution is wrong! What happens if the input is aaa and bbb. You need to have a third loop to check if the counts are all 0 for each.