String

• Immutable

• if you need to mutate => use StringBuilder

• .toCharArray()

  • char[] characters = abc.toCharArray();

• indexOf(...)

  • "computer".indexOf('c') = 0

  • "computer".indexOf('a') = -1

  • "computer".indexOf("puter") = 3

• Like arrays, Strings are variable in size This one might be obvious, but it bears repeating. In most languages, arrays are treated as a collection, whereas we think of a string as a single “thing”. However, remember that it’s still an array of characters on the backend, so the space the string takes up AND the amount of time it takes to do things like generate a hash of a string are proportional to the length of the string.

Common Mistakes in Interviews Featuring Strings

Viewing String Problems As "Easy"

Strings, despite being one of the first data structures introduced to programmers, shouldn't be underestimated as "easy" in interview scenarios due to their versatility. Unlike data structures like trees or graphs that have specific algorithms like DFS/BFS or backtracking respectively, strings can incorporate a range of technical topics frequently asked in interviews. Strings are a linear data structure, and because of that all common algorithms related to linear data structures could potentially be involved in a string question. This means techniques like two pointers, sliding windows, recursion, backtracking, and dynamic programming (to name just a few) can be used in a string question. Therefore, avoiding string practice due to perceived ease could lead to challenges in handling complex string problems in interviews.

Messing Up String Conversions

One of the more annoying things we can have to do, which nevertheless comes up fairly often, is various forms of string math. This includes converting characters to their index in the alphabet and converting characters to their numeric value. General familiarity with how to do these things in your interviewing language is critical. It's obscure enough to not remember on the spot, but simple enough that it looks bad if you don't know how to do it.

Making Assumptions About String Contents

It's easy to think of strings as just letters in the alphabet, but this will lead to one of the most common interview errors with string questions – making an incorrect assumption about the string contents. Useful clarifying questions to ask whenever strings are involved in a problem can be questions like.

• Are we guaranteed that there will just be alphabetical characters? Alphanumeric?

• Do we need to worry about punctuation?

• Do I need to handle special characters/symbols?

• Can the string ever be empty or null?

• Is the string always lower/uppercase? Can we receive a mixed case string?

• Do we need to worry about the string encoding at all? UTF-8, ASCII, etc?

• Does the string fit into memory?

Here's a good example of a string question where all of these questions matter in achieving the correct output to pass all tests. Don't make assumptions about what is in the string, asking these types of questions helps demonstrate your seniority and familiarity with common gotchas.

Hidden Complexity

One danger you should be aware of is how languages will abstract away the heavy lifting when it comes to strings. This can make us wrongly assume that "simple" operations are cheap. 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 we may assume that this 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.

One great feature of Java is the StringBuilder class. This class provides a performant way to modify and append onto a string by using an array as the underlying data structure. StringBuilder also provides a nice toString() method that we can use to recover a string.

C uses an array as the underlying data structure which prevents the language from masking additional complexity. With that said, we have to be careful when allocating an array in C. The size of the array is static which means all of the memory needs to be allocated up front!

String Operation	Description	Time	Space
Length	Returns the number of characters in the string.	O(1)	O(1)
Index Access	Accesses a character at a specific position in the string.	O(1)	O(1)
Concatenation (+)	Combines two strings into one.	O(n)	O(n)
Traversal (e.g. for loop)	Goes through each character in the string one by one.	O(n)	O(1)
Naive Search (e.g. contains, index of)	Searches for a specific character or substring in the string.	O(n*m)	O(1)
Substring	Creates a new string that is a subset of the original string.	O(m)	O(m)

• n represents the length of the string

• m represents the length of the substring

This above table is a generalized view of string operations, but it's worth mentioning that the details will differ depending on your particular language. For example, in some Java versions, the substring operation was O(1) in space complexity as it shared the same character array with the original string, but this has been changed in more recent versions to avoid memory leaks, leading to O(s) space complexity, with m as the length of the substring.

Advanced String Topics

Are strings anagrams

// https://www.youtube.com/watch?v=6W_Fve7qIe4&t=726s

// abcs, basc => are anagrams (same chars in arbitrary order)
public class AreStringsAnagrams {
	
	public static boolean isAnagram(String s1, String s2) {
		if (s1.length() != s2.length()) return false;
		s1 = s1.toLowerCase();
		s2 = s2.toLowerCase();
		
		int[] letters = new int[256];
		for (char c : s1.toCharArray()) {
			letters[c]++;
		}
		for (char c : s2.toCharArray()) {
			letters[c]--;
		}
		for (int i : letters) {
			if (i != 0) return false;
		}
		return true;
	}
}

The Multiple Pointers Technique

Same as with arrays, it is common to use multiple pointers to traverse a string. This allows us to accomplish various interesting tasks with substrings and comparing characters. Here are some problems to consider:

• Reverse words in a string
• String compression

String compression ("aaabccc" -> "a3b1c3")

// https://www.byte-by-byte.com/stringcompression/
public class StringCompression {
	/*
	compress(“a”) = "a"
	compress(“aaa”) = "a3"
	compress(“aaabbb”) = "a3b3"
	compress(“aaabccc”) = "a3b1c3"
	 */
	public static String compress(String s) {
		StringBuilder result = new StringBuilder();
		int sum = 1;
		
		for (int i = 0; i < s.length() - 1; i++) {
			if (s.charAt(i) == s.charAt(i+1)) {
				sum++;
			} else {
				result.append(s.charAt(i)).append(sum);
				sum = 1;
			}
		}
		result.append(s.charAt(s.length()-1)).append(sum);
		return result.length() < s.length()? result.toString() : s;
	}
}

The Sliding Window Technique

Sliding windows are common with any linear data structure. That includes things like arrays, linked lists, and, of course, strings. They are a great tool for finding the longest substring matching an arbitrary property. For practice take a look at the following.

• Longest substring without repeating characters
• Longest substring with at least k repeating characters
• Find all anagrams in a string

Advanced String Algorithms

These advanced algorithms are fairly niche and only likely to be asked at FAANG companies, and even then these algorithms show up a small fraction of the time. If you want to go deep on strings, there are three advanced algorithms worth having on hand. All of these algorithms are used for searching for a substring within a string and variations of them exist in a handful of problems online. The core algorithms to learn are:

• KMP
• Boyer Moore
• Rabin-Karp

Regular Expressions

While it is unlikely that you will get a problem which can be solved directly with regular expressions, you should have a good idea of how regular expressions work. Leetcode questions with regular expression answers do exist, but are uncommon. If you're thinking of using regular expressions in your solution, you're probably over-complicating it. With that stated, it is still important to have familiarity with them. Consider playing with a site like regex101.com to develop a better sense of regular expressions. Additionally, spend some time thinking through how to document a regular expression. Demonstrating not just an understanding of regular expressions but how to make them maintainable shows a certain coding maturity.

Language-Specific Advice

Up to this point, all the advice we have given has been language agnostic but various languages handle strings very differently. In this section, we will cover features of four popular language choices: Java, C++, Python & JavaScript.

Java Strings

Fast Facts:

• Mutable? No

• Primitive? No

• Comparison: s1.equals(s2)

• Access the ith character: s1.charAt(i)

Useful Java String Methods:

Method	Description	Time	Space
s.length()	Returns the length of the string	O(1)	O(1)
s.charAt(int i)	Returns the character at index i	O(1)	O(1)
s.substring(int i, int j)	Returns substring from i to j (inclusive of i, exclusive of j)	O(j-i)	O(j-i)
s.contains(String s)	Returns True if s is contained in the string	O(1)	O(1)
s.indexOf(String s)	Returns the starting index of the first occurrence of s	O(n)	O(1)

/* Strings are OBJECTS */
// Primitives in Java are lowercase and include data types like:
double foo = 76.762121;
char bar = 'i';
boolean baz = true;

// Strings are *Objects*
String s = "Interviewing.io";


/* String comparison doesn't use the == operator */
String a = "Interview";
String b = "Interview";

// This outputs false because == compares the Object pointers not values
System.out.println(a == b); 
// This outputs true because equals() compares the values of the strings
System.out.println(a.equals(b));


/* Comparing Object pointers uses the == operator */
String c = a;
// This outputs true since a and b point to the same object in memory
System.out.println(a == c);

Common String algorithms

I’ve already discussed Strings at length in this post, so I won’t go into a ton of detail here. However, to reiterate, these are the String algorithms that you need to know:

• Using 2 Pointers Same as with arrays, it is common to use multiple pointers to traverse a String. This allows us to accomplish various interesting tasks with substrings and comparing characters

• String Math One of the more annoying things we can have to do, that nevertheless comes up fairly often, is various forms of string math. This includes converting characters to their index in the alphabet, converting characters to their numeric value, converting Strings from String to integer, and more. General familiarity with how to do these things is critical

• String Sliding Windows Again, similar to arrays, sliding windows are common with Strings. They are a great tool for finding the longest substring matching X property

• String Comparison, Alignment, and Matching One of the common things we might want to do with strings is to compare them in some way. For example, do two Strings match? What is the best way to align two Strings to minimize the difference between them.

• Regular Expressions Now you DEFINITELY don’t need to become an expert on regular expressions for your interviews, but at least understanding the basics of wildcard matching and how to construct simple regexes will be very helpful. It is also good to understand how to use regular expressions in your language of choice.

• Named String Algorithms I don’t recommend spending a lot of time on these, but if you really want to go deep on Strings, KMP, Boyer Moore, and Rabin-Karp are good algorithms to explore further.

Practice String coding interview questions

Here are some common String coding interview questions. I highly recommend practicing these as you would solve problems in an actual interview.

• String Compression
• Anagrams
• String Deletion
• Longest Common Substring
• Permutations of a String