Strings

While this book assumes you’ve had at least an introduction to computer programming, this chapter and the next will contain an exploration of some basic computer science concepts in order to create a baseline of understanding for the content to follow. If you come across something in this chapter that you already know feel free to skip ahead.

Strings¶

Strings are (of course) one of the most commonly used data structures in programming. The documentation of most programming languages starts with the ubiquitous “Hello World” program, which usually involves rendering a string.

In Python, for instance, all that’s required to render text to the console is a simple print statement:

print("Hello World")

This outputs the 10 characters comprising the string “Hello World.”

Or is it 11 characters? 13? Something else? To understand how to manipulate strings, you must begin by understanding the way in which they’re constructed and represented by computer operating systems and programming languages.

Breaking Down a String¶

In most programming languages a string is nothing more than an array with a character at each position. Often, but not always, the final character will be a “null” character, which is a character that represents the end of the string. Dating back to the days of the teletype (if you’ve ever seen an old movie where a machine is typing out a message on a piece of paper, that’s a teletype), the null character was used to indicate the end of a line in the message or the end of the message. The tradition remains in some modern programming languages, and sometimes in manipulating strings not accounting for the null characters can cause problems. For the remainder of this book that you don’t have to worry about it, but you’ve been warned.

Arrays are covered in the next chapter, but let’s begin by discussing what is meant by a “character.” If you’re already familiar with this subject, please feel free to skip this section.

Whenever you press a key on your keyboard, like I’m doing to write this book, a character comes out on the other end. Without going into too much detail on exactly what happens during this process, the electrical signal generated by the key is sent to the operating system, which then uses a character “lookup table” to look up the character represented by that signal. The two most commonly used lookup tables for computers that use Latin-character-based languages (like English) are ASCII and Unicode. Again, there are piles of documents written about these two systems and others, and if you’re interested a quick web search will show you more than you ever needed to know about these two systems.

The positions of the characters in this table are direct descendants of the teletype systems that were widely in use in the middle part of the 20th Century. If you’re watching a movie and you see a chattering machine spitting out the latest news or a top-secret message that needs to be seen immediately by the people in charge onto a sheet of paper one line at a time, that’s a teletype machine. It might be hard to imagine, but not all that long ago computers were only able to output to printers and not screens.

The size of a character in most operating systems is based on a byte. A byte contains eight bits. A bit is a symbol that can contain a one or a zero. Since each bit can represent two states, the number of signals that can be represented by a given number is bits is $2^n$, where n is the number of bits.

For instance, 2 bits can represent 2², or 4 discrete states: [0, 0], [1, 0], [0, 1], and [1, 1]. Three bits can represent 2³ or eight discrete states. 2⁴ is 16 states, 2⁵ is 32 states, etc. While there are LeetCode questions that cover binary numbers, they’re beyond the scope of this book. There are piles of information available that cover computer operating systems and binary mathematics, and if you have more of an interest in the subject I encourage you to look them up.

A byte, which contains eight bits, can represent 2⁸ or 256 discrete states, and so most character systems are based on a representation of 256 characters. Usually, the first 128 of these characters are reserved for “regular” keys on a keyboard, while the second 128 are reserved for “special” characters. So when you press that ‘d’ key on your keyboard, it sends a numeric symbol to the operating system which then looks up which character is represented by that number. In the case of an English keyboard, the lowercase ‘d’ is represented by the decimal number 100. (This is not the same as the uppercase ‘D’, which is represented by the number 68.)

There’s nothing special about the positions of these characters. If you grew up speaking a language other than English, you’ve probably used a keyboard where the characters are in different positions than they are on an English keyboard. That same ‘d’ key on a different keyboard might instead stand for “M”, or “7”, or “Ü”, or “α”. It all depends on how the keys are mapped in that lookup table. The reason why should be clear: it’s easier to change a look-up table than it is to rebuild a keyboard!

Understanding Character Sets

Whole books have been written on how computers handle and manage text, but for the most part it’s so automatic most of us rarely take the time to stop and think about it. Ever since the proliferation of “web fonts,” having to move between different character sets is something that has become nearly effortless to do. There is a rich history behind how we got to this point, however, and while it’s unlikely to come up in most programming interviews, it certainly won’t hurt to know the difference between Unicode and ASCII, or to know that the “ISO-8859-1” character set is the same as the “Latin-1” character set. These kinds of issues do come up in situations where developers are dealing with internationalization or accessibility, and it’s good stuff to know if your web site or application needs to handle both English and Chinese character representations, for instance, and what the differences are between the two language representations at the level of code.

So when computer programmers talk about “characters,” this is what is meant. A series of symbols mapped to a lookup table, that translates them to the corresponding electrical signal represented by a keyboard key. None of that is likely to come up as an interview question, but it’s a basic idea that it’s important to understand as a developer.

Another important thing to know is that not all characters are visible characters. The “space”, “tab”, “return”, and “enter” (not always the same as return!) characters — and others — are mapped to the lookup table the same as visible characters, and have to be accounted for when you’re parsing strings. These characters are sometimes called “escape” characters since they can only be represented in strings using a symbol preceded by a backslash (\). A “tab”, “space”, and “newline” are meaningful symbols to many programming languages and so you can’t always just type them into a string. Instead you must type a tab character as \t. A return is \r, newline is \n, even a space must sometimes be escaped to mean a string as a character and not a symbol that a programming language needs to consider.

These are all things to keep in mind when you hear the word “character.” When you hear the phrase “array of characters” you should immediately think of a string, and vice-versa. And when you think of either you should picture that array as potentially containing the visible and non-visible characters that can be found in a table stored somewhere in the operating system.

Here’s another look at that image above one more time:

Accessing a String¶

As mentioned before, usually the first thing a programming student is shown how to do is generate output using some kind of variation of a “print” statement. You won’t be asked interview questions about that. What you might be asked questions about, however, is the ways in which you can manipulate strings to get the results you need to accomplish the task you want.

I recently was working for a client that needed data parsed from an Excel document to the web. Among many of the things complicating this task was that we on the programming team had no control over what was in the Excel document. This means that many of the cells in Excel were “polluted” with data that kept our parsing program from running properly.

For instance, many of the cells contained line returns, or the “\n” character. This interfered with our program, because when we wanted to put a piece of data into a specific place if we printed it with the line return it would knock all of the data after it out of alignment. I used the Python Panda’s strip() command to get rid of these unwanted characters, but even this was limited in its effectiveness as it only considers items at the beginning and end of a string. The team eventually had to use some custom lambda functions to get the results we wanted. This is not an uncommon problem to face as a developer, and so knowing how to slice-and-dice strings is a very useful skill to have. Parsing string data is absolutely something you will do more than once in your programming career.

Typecasting¶

Everyone knows that 2 + 2 = 4, but while that’s fine for English or mathematics, that’s not necessarily the case at all when it comes to programming languages. For starters, “=” is the assignment operator, which means that 2 + 2 = 4 will return an error. Additionally, do you as a programmer mean the expression 2 + 2 = 4 or do you mean the string “2 + 2 = 4”? Notice that one is in quotes and the other is not, because one is an expression and the other is a string.

Context is important in computer programming. Compilers really can’t be bothered trying to figure out what it is you, the programmer, are trying to do. They don’t care. They’re literal, and logical.

If you’re trying to evaluate whether 2 + 2 = 4, the correct expression is:

>>> 2 + 2 == 4
True

Enter "2" + "2" == 4 however, and what seems true is now false.

>>> "2" + "2" == 4
False

The reason for this is that like most programming languages, Python treats strings and symbols separately. 2 without quotes is the “symbol” for 2. It means the number 2 which is exactly what you think it means. 2 fingers, 2 sisters, 2 dollars.

“2” is the string representation of 2, which doesn’t mean anything to Python except that it’s a string. It’s a character with no built-in function except to display pixels in the form of the number 2.

So what happens when you get the string “2,” but what you really need is the number 2? Most languages provide type conversion functions like int() in Python or parseInt() in JavaScript, where parseInt("2") will return the integer number 2.

Built-in String Functions¶

Most programming languages contain a number of functions for manipulating strings. One of the more basic and widely used is the “concatenation operator,” which connects one string to another.

myVar = "Hello" + "world!"

The plus in this instance does not mean addition, it means concatenation, or joining together. Eagle-eyed readers may have noticed that this concatenation may have an unwanted result.

print(myVar) HelloWorld!

Oops! Where did the space go? There are multiple ways to account for it, including adding it to the first or second string in the concatenation, but the object here is to make you aware that you need to account for it when processing your data.

Processing strings is an important part of data science, and so knowing how to do it is a fundamental skill all programmers must possess. As such, you absolutely should know how at least the basics of string processing, and the built-in functions most languages contain. Built-in string functions are also a great place to start building up your programming interview skills, as knowing how to build each of the following functions from scratch will help you gain a lot of skill in string and character processing.

While these functions may differ in name from language to language, they’re all available to you as a programmer interested in manipulating strings:

length() or len() or sizeof() These are different names for functions that return the length of the array that is passed to them. This is incredibly useful for processing strings because it allows your code to handle strings of whatever size is passed to it.

myVar = "Hello world!"
print(len(myVar))
# prints 12

toUpper() or toLower()

These functions will change every character in a string either to upper or lower case, as the function name suggests. This can be invaluable for data entry.

split() This function will split an array element into pieces according to a delimiter. When the delimiter is left empty, every element of the array will be split into an element of its own. This function has different implementations, depending on the language, so examples of splitting strings into individual characters in different languages are shown below. The C++ standard libraries don’t have a straightforward way to accomplish this task, and the easiest way to do this in Java uses a regular expression, so if you’re focused on those languages you will have to either look up these implementations, or, better yet, build your skill by writing your own!

Python:

myString = "algorithms"
print([*myString])
# Prints ['a', 'l', 'g', 'o', 'r', 'i', 't', 'h', 'm', 's']

JavaScript:

console.log('algorithms'.split(''))
// Prints ['a', 'l', 'g', 'o', 'r', 'i', 't', 'h', 'm', 's']

join()

The join function is the opposite of split, and it can be used to bring separate items together into a single string. For instance, the concatenation example given above could just as easily have been written as:

myVar = "".join(["Hello", "world!"])

The empty string just before join is known as the “delimiter,” and it’s what will be used to separate the items in the array as they’re concatenated into a single data object.

myVar = " ".join(["Hello", "there,", "big", "wide", "world!"])

Will set myVar to “Hello there, big wide world!” There’s nothing special about the string used as the delimiter. You can put anything you want inside as long as it’s a valid character. I chose a space in this example, but I could have also chosen multiple characters, dashes, or even a line return.

Note the comma both inside and outside of the quotes surrounding the second object in the array. As mentioned before, the comma inside the quote is the character representation of a comma, while the comma outside the quotes is a symbol that tells Python to distinguish between the items in the array.

index() or indexOf()

Most programming languages contain a function that returns the first index of a given item in an array, which makes it an incredibly powerful search tool for some of the algorithms that will be presented in this chapter and the next. For example:

first_o = "Hello world!"
print(first_o.index("o"))

This will print 4, because the first “o” in the string “Hello world!” can be found at position 4.

slice() and splice()

Slicing and splicing are two methods that allow work to happen on subset of a given string. The slice method usually has to do with selecting a range of items from a string, while the splice method usually has to do with performing an operation on a range of items in the string. These operations may include removing or replacing items in the string, or adding — splicing — new items into the string.

I’m mentioning them together because they work in similar ways, and because they form the basis of what can be done with string in most programming languages. I’m focusing on both Python and JavaScript in these examples because JavaScript has explicit keywords for performing these operations, while Python has a more implicit way of doing it, and between the two you can see how these operations are constructed in most programming languages. In both cases, the operations take the form of:

item.slice(start position, end position, step)

The item is the string or array on which you mean to operate. “slice” or “splice” are the keywords used to indicate the type of operation, although in Python, again, these keywords are implicit as will be shown momentarily.

“Start position” and “end position” should be self explanatory — the indices of the items you want to select. Be careful though: what these indices represent may not be what you expect, and can even be different from language to language. Usually start position is the index of the first item you wish to select, but the end position is the index of the item before the one you wish to select.

let myVar = 'Hello world!'
myVar.slice(0, 5) // selects "Hello", the first 5 characters in the string

Notice that the “o” is at position 4 in the string, which means that slice stops just before the space character at position 5.

I keep mentioning that Python is more “implicit”, and here’s what I mean by that. There is no explicit keyword for “slice” in Python, with the operation instead being performed by the colon “:”.

myVar = "Hello world!"
myVar[0:5] # selects "Hello", the first 5 characters in the string

This does the exact same thing as the JavaScript example above, but the keyword “slice” is simply not needed.

Before diving into further differences between the two languages, let me explain the “step” parameter. “Step” is an optional parameter that indicates how many steps you wish to take in selecting items. As of this writing, JavaScript does not support passing a step parameter, but Python does. (There are rumors that more Pythonic string manipulation will arrive in future versions of JavaScript, and there are of course numerous libraries and bits of code that can be used to make the dream a reality.)

If I wanted to return every other item in a string, I could pass a third parameter in Python.

myVar = "Hello world!"
myVar[0:12:2] # selects "Hlowrd", every other character in the string.

Python (but not JavaScript) allows for leaving out the start and or end parameter, allowing the language to fill in the blanks itself. For instance, if I wanted to select from the beginning of the string up to its 5th character, I could write:

myVar = "Hello world!"
myVar[:5] # selects "Hello", the first 5 characters in the string

This is equivalent to the example given above where I explicitly stated the start and end positions of the slice operation. Can you figure out how to pass only one value to slice operation and end up with “HloWrd”, the selection of every other character in the string “Hello World!”

Negative indices can also be passed to these functions, which allow you to choose from the end of the string instead of the beginning. These work the same in Python and JavaScript. For example, to selected the last 6 characters in a string, minus the last one, you could use:

myVar = "Hello world!"
myVar[-6:-1] # selects "world", a sequence beginning at the 6th character from the end and ending at the 2nd character from the end.

Now that we’ve covered the basics on slicing, and selection, Let’s turn our attention to splice(). There are subtle difference between the two, and the difference usually have to do with the way in which the data is modified returned. Again, I’m going to focus on both JavaScript and Python with the hope that it covers the bases of how splicing is implemented in most programming languages.

The form of splice() in JavaScript is:

splice(start, length, item)

These parameters are similar to — but not the same as — the parameters for slice(). start is the same, the index of the item you want to start with. length, however, is different. Instead of being a pointer, length indicates a range — specifically the the number of items you want to select. item is optional and indicates the item you want to insert into the string at the position indicated by start. Let’s look at a first example without using item:

myVar = ['Monday', 'Tuesday', 'Wednesday', 'Friday', 'Saturday', 'Sunday']
myVar.splice(2, 3) // Returns "Wednesday", "Friday", "Saturday"

If you’re sharp, you may have noticed that there is no “Thursday” in the myVar array. Let’s fix that using splice():

myVar = ['Monday', 'Tuesday', 'Wednesday', 'Friday', 'Saturday', 'Sunday']
myVar.splice(3, 0, 'Thursday') // Adds "Thursday" to the array at position 3

Keep in mind that unlike slice(), splice(), in JavaScript, modifies the original array. Once you’ve spliced Thursday into myVar, it’s there as if it had always been there. You cannot recover the original array without first either making a copy of it, or using the JavaScript toSpliced() function which I’m not going to cover here. Just be aware of this modification when using splice() in your code. Maybe JavaScript linters or code libraries will warn you against programming “side effects,” which you can easily cause if you’re not careful with splice(). Python does not have this particular issue with side effects, as it will always return a copy of the data you’re working with, and not the original data.

Python does not have a built-in splice() function, but you can use Pythonic concatenation methods to achieve the same result.

myVar = ["Monday", "Tuesday", "Wednesday", "Friday", "Saturday", "Sunday"]
myVar = myVar[:3] + ["Thursday"] + myVar[3:]

Immutability, Side-Effects, and Strings

When you’re working with strings, or any other piece of data, it’s important to understand the way in which your functions are changing the data you’re passing to them. A lot of programming courses will say things like “don’t use global variables,” or “your functions must be pure,” but what do these things mean, exactly?

A “pure” function is a function that doesn’t change the data it’s passed, or any other data for that matter. It returns a copy of a value, and that’s it. Why does this matter? Imagine you have a game that keeps a score, and you want to keep track of the score in a variable. If you’re creating a game and you have a function that changes the score, you want to be sure that the function is only changing the score, and not anything else. It should not change the player turn, the number of lives remaining, or the bonus multiplier.

The reason why is because as the game grows in scale and complexity, it can become harder and harder to figure out what’s going what, and what’s going wrong. When multiple pieces of functionality are bound up in a single function, it can be hard to break out that functionality to be used in other parts of your program.

When it comes to strings, you want to be very careful that any manipulations you perform on a string are not causing unintended consequences, or “side effects.” It’s usually important to keep a copy of the original string, and if it needs to be transformed to transform it in a way that doesn’t change the original string. In fact, in many languages, strings are immutable, which means they can’t be changed at all. In designing your own string functions, it’s important to consider whether or not you want to make your strings mutable (probably not), or keep them immutable and only return transformed copies of the original. Either way, it’s important to consider consequences of that decision, and you are likely to be asked about string immutability and/or side effects in a coding interview.

Python’s slicing operations always return a new copy without modifying the original, unlike JavaScript’s splice() which modifies the array in place. While Python doesn’t have a splice() function, its flexible slicing syntax with the colon operator (:) allows you to achieve similar results through slice assignment or concatenation, as shown in the “Thursday” example above.

Be careful when using these functions in different languages as they all work slightly differently, and the difference usually has to do with how the range of items is chosen. For example, in Python, you can use a “:” to select the range of the items you’re interested in. Arrays start at 0, and the second value in a splice parameter is the item before the one in the number.

Python:

>>> myVar = ["turtle", "gecko", "frog"]
>>> myVar[1:2] # select from position 1 to before position 2
['gecko']
>>> myVar[:3] # select everything up to and including position 3
['turtle', 'gecko', 'frog']
>>> myVar[2:] # select everything after position 2
['frog']
>>>

Javascript:

let myVar = ['turtle', 'gecko', 'frog']
console.log(myVar.slice(1, 2)) // select from position 1 to before position 2
// Prints ["gecko"]
console.log(myVar.slice(0, 3)) // select everything up to and including position 3
// Prints ["turtle", "gecko", "frog"]
console.log(myVar.slice(2)) // select everything after position 2
// Prints ["frog"]

Learning Multiple Languages

A basic understanding of multiple programming languages and paradigms can be a very useful thing for a developer to know. This does not mean you have to become an expert in every programming languages, but seeing how different languages implement the same functions can give you a broader appreciation and context for the way programming languages are constructed.

The first programming language I learned in depth was C, and because C is that language from which so many later languages are derived, the basics of C have been applicable to every language I’ve learned since. C is a compiled language, and many front-end languages are interpreted, and interpreted languages don’t have a lot of the same overhead that compiled languages do. That makes them easier to learn, but some of the nuances of things like library imports, memory management, input/output control, and error handling are relatively unknown to front-end developers.

Python, is an interpreted language, and so it’s easier to learn than C, but it’s also a very powerful language that can be used for a wide variety of tasks that are not as easily accomplished with JavaScript. Similarly, JavaScript has a number of built-in functions for working with web browsers that are not available in Python. There are also lower-level functional programming languages like Haskell and Lisp that are very different from Python and JavaScript, as they require developers to be very efficient and precise when defining and using functions.

The more languages you spend time with, the greater appreciation you’ll have for the language you’re an expert with, and the more you’ll understand why certain languages are better suited for certain tasks than others. Again, I’m not saying you need to take a 40-hour course in SmallTalk, but it’s definitely worth your time to spend a few hours “dipping in” to a few different languages to see how the work.

In addition to the ones I’ve already mentioned, Java and Rust are two languages that front-end developers should be basically familiar with, as they are widely used in the broader “full-stack” on which frontend applications are built.

Reversing¶

Let’s start with one simple example of a question that can be resolved in a number of ways, to show how a combination of built in functions and programming paradigms can be used to solve a problem. How can you reverse a string, without using a built-in “reverse” function?

Here’s the answer to the reversing exercise above. The simplest and most straightforward way to reverse a string — which is an array, of course — is to use a for loop:

def reverseString(myString):
  reversed = ""
  for i in range(len(myString)- 1, -1, -1):
    reversed += myString[i]
  return reversed

This is straightforward, easy to understand, and it works. But can it be improved? Is there a “better” way to do it, without using a for loop? Of course that was a rhetorical question, and the answer is “yes!” Look again at built-in string functions we discussed earlier.

def reverseString(myString):
  return myString[::-1]

Both approaches are O(n) - why? Does the more concise slicing approach offer any advantages? When might you prefer one over the other?

📝 NOTE

When you use built-in functions always be aware that some of them might modify the data they return, and some might not. See the section on “Immutability, Side-Effects, and Strings” later in this chapter for a list of things to keep in mind when working with strings.

I will revisit the construction of some of these functions in the upcoming “Arrays” chapter, but hopefully this has helped you start to see the importance of these basic string manipulation problems and why they might come up in programming tests.

Example Questions¶

These next few example questions will give you a taste of what’s coming in Chapter 4. Try to solve the following problems without looking ahead to that chapter. Or, if you get really stuck, come back and solve these problems after reading the next chapter.

Palindromes¶

A palindrome is a string of text that contains the same characters in the same order both forwards and backward, excluding spaces and punctuation. Some simple one word examples are the words “civic,” “level,” and “radar.” Palindromes can also be comprised of entire sentences, or even paragraphs. The sentence “Evade, Dave!” is a palindrome because without the capitalization, comma, space, and exclamation point the letters are “evadedave” which are the same forwards and backwards. Write a function that determines whether or not a given string — minus the punctuation — is a palindrome. If you get it working with the example given, search the internet for other examples of palindromes to test your function.

Maximum and Minimum Element¶

Given an array, can you return the highest or lowest element according to a given criteria?

Example: What is the largest number in the array [7, 2, 8, 6, 5]?

Longest Substring Without Repeating Characters¶

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = “abcabcbb” Output: 3 Explanation: The answer is “abc”, with the length of 3. Example 2:

Input: s = “bbbbb” Output: 1 Explanation: The answer is “b”, with the length of 1. Example 3:

Input: s = “pwwkew” Output: 3 Explanation: The answer is “wke”, with the length of 3. Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.

Finding a Character or Word in a String¶

Create a function that takes a string and a character and returns the position of that character in the string. For instance, given the string “One tall house, one tall ladder” and the character “a”, the function would return 5. Notice that there are three "a"s in the string. How would you return the positions of all of them? Does your function account for capital and lower-case letters?

Similarly, create a function that takes a string and returns the position of a word. Given the same string as above, find the position of the word “tall.” Again, as above, account for the fact that there is more than one instance of “tall” in the string. What if the word you’re given is part of a larger word? The word “add” can be found inside the word “ladder.” Does your algorithm work for the cases in which this is and isn’t a valid solution to the problem? Can you think of any other things that should be considered in solving this problem?

Debuggers and Stepping Through Code

Unless you have a photographic memory, it’s going to be hard to come up with the right answer if it uses code you don’t understand. It can sometimes be a real challenge to just look at a piece of code and know exactly what it does.

Many of us — especially web developers — check our code using logs to the browser console. There’s nothing wrong with that at all, but it’s not the most effective way to examine code that isn’t running in an a browser. For that, you need a debugger.

A debugger is a tool that helps you walk through code a step at a time, and provides you with feedback about what is happening in each step. There are so many different debuggers available and so many ways to debug code that I’m not going to try to cover them in this book, but every IDE has one. Or, if you’re not using an IDE, Python has a built-in debugger called ‘pdb.’

You use a debugger by setting a “breakpoint” in your code, which is an instruction to stop the debugger at a given line. When the code frozen in time at a specific line, you can take a moment to examine what’s going on in a function so you can better understand how things are changing.

Debuggers also usually include ways to “step” through your code, which means to run it a line at a time, reporting variables, values, and other relevant things as each line executes.

So again, unless you understand code in just a glance — in which case I seriously doubt you’re reading this sentence right now — pick a debugger to get started with, learn how to use it, and use it to become familiar with the solutions presented in this book. Debuggers can be a bit tricky to get started with, but the learning code isn’t as steep as it looks, and the payoff is huge!

Food for Further Thought¶

Look up the Rabin-Karp algorithm for finding a substring in a string. You probably use this algorithm often as it’s the one behind finding text in a document, like when you push CTRL-F. The Rabin-Karp algorithm works by converting the substring to a hash value which allows it to run in O(n) time. Hashes will not be covered until Chapter 8, but try to begin thinking about Rabin-Karp now. Is it a suitable algorithm to be used in a coding interview? Why or why not?

• Consider adding coding questions to the end of sections **