Strings as arrays of characters
A string is stored the way an array of numbers is, with one character in each slot. The characters sit side by side in memory, each has an index counted from 0, and reading s[i] takes one step however long the string is. The computer stores each character as a number, its character code. Here is the word listen with the code of each of its characters:
index 0 1 2 3 4 5character l i s t e ncode 108 105 115 116 101 110Because a string is an array, the algorithms that read an array of numbers also work on a string. Unlike most arrays of numbers, a string usually draws its characters from a small set. Lowercase words use only 26 different characters, and plain English text uses codes below 128, so a table with one entry for each possible character stays small however long the string is. The first three problems in this lesson are solved with such a table. If reading, slicing or building a string is new to you, Start coding's Strings lesson covers those operations.
Count letters to compare two words
Two words are anagrams when one is a rearrangement of the other: they use the same letters, and each letter the same number of times. listen and silent are anagrams, because each is made of one e, one i, one l, one n, one s and one t.
You get two strings s and t. Return true if t is an anagram of s, and false otherwise.
Constraints
-
s.length,t.length sandtcontain only lowercase English letters
Sample 1 · Input
s = "anagram", t = "nagaram"
Output
true
Sample 2 · Input
s = "rat", t = "car"
Output
false
In the first sample, anagram and nagaram both have three a's and one each of g, m, n and r. In the second, rat has a t where car has a c.
The direct way to check is the one you would use on paper. Take the letters of s one at a time, find the same letter in t, and cross it off so that it cannot be used twice. If some letter cannot be found, or letters of t are left over at the end, the words are not anagrams. Each search starts from the front of t and can read a large part of it. Take the largest input the constraints allow, two strings of 50,000 a's. The search for the -th letter reads letters, the that are already crossed off and then a free one, so in total the searches read
At the rule-of-thumb rate of simple steps a second, that is more than 12 seconds of work.
Sorting gives a much faster check. With its letters sorted, listen becomes eilnst, and so does silent: two words are anagrams exactly when their sorted letters are equal. In Python that test is sorted(s) == sorted(t). Sorting 50,000 letters takes about comparisons, so this method passes with room to spare.
Sorting still does more than the problem needs. Whether two words are anagrams depends only on how many times each letter appears, so it is enough to count. Keep one counter for each of the 26 letters, all starting at 0. Add 1 to a letter's counter each time the letter appears in s, and subtract 1 each time it appears in t. A counter ends at 0 when its letter appears the same number of times in both words, so the words are anagrams exactly when every counter ends at 0.
For rat and car, the counters for a and r go up to 1 and come back to 0, but the counter for t ends at 1 and the counter for c ends at , so the answer is false.
The 26 counters go in one array, and a letter's counter is found from its character code. The lowercase letters have consecutive codes, from 97 for a to 122 for z, so subtracting 97 from a letter's code gives an index from 0 to 25:
| Letter | Code | Index |
|---|---|---|
| a | 97 | 0 |
| e | 101 | 4 |
| t | 116 | 19 |
| z | 122 | 25 |
In Python the index is ord(ch) - ord("a"), where ord gives the code of a character.
Step through the counters
Step through listen and silent below: each letter of the first word raises its bar by one, and each letter of the second word lowers it again. Then try rat and car, which leave the bar for t at 1 and the bar for c at , or type your own pair of lowercase words.
Here is the check as a function, run on the two samples:
def is_anagram(s, t):
if len(s) != len(t):
return False
count = [0] * 26
for ch in s:
count[ord(ch) - ord("a")] += 1
for ch in t:
count[ord(ch) - ord("a")] -= 1
for c in count:
if c != 0:
return False
return True
print(is_anagram("anagram", "nagaram"))
print(is_anagram("rat", "car"))[0] * 26 makes a list of 26 zeros, one counter per letter.
The function compares the lengths first, because words of different lengths cannot be anagrams, and it returns false for them without counting anything. For words of lengths and , the first two loops make counter updates and the last loop reads the 26 counters. On the largest input that is 100,026 steps. Crossing letters off took over a billion. The 26 counters are all the extra memory the function uses, however long the words are.
Remember what each character was paired with
In the anagram check, the table entry for a character held a count. An entry can hold anything we need to remember about its character. In the next problem it holds another character.
You get two strings s and t of the same length. They are isomorphic if you can replace characters of s to get t, where every copy of a character is replaced by the same character, and no two different characters are replaced by the same one. A character may be replaced by itself. Return whether s and t are isomorphic.
Constraints
-
s.length t.lengthequalss.lengthsandtcontain any ASCII characters
Sample 1 · Input
s = "egg", t = "add"
Output
true
Sample 2 · Input
s = "f11", t = "b23"
Output
false
Sample 3 · Input
s = "paper", t = "title"
Output
true
In egg and add, e is replaced by a and both g's by d. In f11 and b23, the character 1 would have to become 2 at index 1 and 3 at index 2, so the answer is false. paper becomes title by replacing p with t, a with i, e with l and r with e. All the replacements happen at once, so the e that r turns into is not replaced again.
To check a pair of strings, read them together from left to right and record each replacement the first time it is needed: the table entry for the character of s gets the character of t at the same index. When the same character of s comes up again, the character of t at that index has to be the one in the entry. On f11 and b23, index 1 records that 1 becomes 2, and index 2 fails, because t has 3 there.
One table is not enough, though. It accepts badc and baba, which should be rejected:
Read from s to t, every character of badc has one replacement: b becomes b, a becomes a, d becomes b and c becomes a. No entry is ever asked to hold two different characters, and yet b and d both become b, which the statement forbids. To catch that, keep a second table that runs the other way and records, for each character of t, which character of s it came from. At index 2, t has b again. The second table already has that b coming from the b of s, so it cannot come from d as well, and the pair is rejected.
The characters are all ASCII, the standard set of codes from 0 to 127 that covers English letters, digits, punctuation and the space. So each table can be a list of 128 entries, one for each code. An entry of means that nothing is recorded for that character yet. to_t is the table from s to t, and to_s is the table from t back to s:
def is_isomorphic(s, t):
to_t = [-1] * 128
to_s = [-1] * 128
for a, b in zip(s, t):
x, y = ord(a), ord(b)
if to_t[x] == -1 and to_s[y] == -1:
to_t[x] = y
to_s[y] = x
elif to_t[x] != y or to_s[y] != x:
return False
return True
print(is_isomorphic("egg", "add"))
print(is_isomorphic("f11", "b23"))
print(is_isomorphic("paper", "title"))
print(is_isomorphic("badc", "baba"))zip walks both strings in step; the problem guarantees equal lengths.
At each index there are two cases. If neither character has an entry yet, the pair is new, and both tables record it. Otherwise the pair is acceptable only if the two entries already name each other, which is what the second condition tests. That condition also rejects a pair in which one character has an entry and the other has none, because an entry of never equals a character code.
Each index costs at most four table reads or writes, so the longest input, 50,000 characters, takes at most 200,000 of them. The two tables hold entries whatever the length of the strings.
Look up each symbol and the one after it
Both tables so far started empty and were filled in from the input. When the meaning of each character is known in advance, the table can be written into the program instead. Roman numerals are an example.
Roman numerals use the symbols I, V, X, L, C, D and M for 1, 5, 10, 50, 100, 500 and 1000. A numeral adds up its symbols, except that a smaller symbol written just before a larger one is subtracted: IV is 4 and XC is 90. Given a valid numeral s, return its value.
Constraints
-
s.length scontains only I, V, X, L, C, D and Msis a valid numeral between 1 and 3999
Sample 1 · Input
s = "III"
Output
3
Sample 2 · Input
s = "LVIII"
Output
58
Sample 3 · Input
s = "MCMXCIV"
Output
1994
III is , and LVIII is : read each symbol, look up its value and add it. MCMXCIV is different, because three of its symbols stand just before a larger one (C before M, X before C, and I before V), and each of those three is subtracted:
So whether a symbol is added or subtracted depends on the symbol after it. Read the numeral from left to right, and at each symbol look up two values, its own and the next symbol's. If the next value is larger, subtract this symbol's value from the total; otherwise add it. The last symbol has nothing after it and is always added. Here is MCMXCIV read this way:
| Symbol | Value | Next symbol | Action | Total |
|---|---|---|---|---|
| M | 1000 | C | add | 1000 |
| C | 100 | M | subtract: | 900 |
| M | 1000 | X | add | 1900 |
| X | 10 | C | subtract: | 1890 |
| C | 100 | I | add | 1990 |
| I | 1 | V | subtract: | 1989 |
| V | 5 | none | add | 1994 |
def roman_to_int(s):
value = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
total = 0
for i in range(len(s)):
if i + 1 < len(s) and value[s[i]] < value[s[i + 1]]:
total -= value[s[i]]
else:
total += value[s[i]]
return total
print(roman_to_int("III"))
print(roman_to_int("LVIII"))
print(roman_to_int("MCMXCIV"))The dictionary value holds the value of each symbol.
The dictionary value is the table. The condition tests i + 1 < len(s) before it reads s[i + 1]. Without that test, the step for the last symbol would read s[len(s)] and stop with an IndexError.
Walk a string from both ends
The three table problems read the string once, from left to right. The next two problems pair each character with the one at the same distance from the other end, so their solutions walk in from both ends toward the middle.
Reversing a string is the simplest case. Reversed, hello is olleh: the characters at indices 0 and 4 have traded places, so have the ones at indices 1 and 3, and the middle character, at index 2, has stayed. In a string of length , the character at index trades places with the one at index . We will call two such positions a mirrored pair.
You get the characters of a string as an array s. Reverse the array in place, so that the first character ends up last and the last ends up first, using only extra memory.
Constraints
-
s.length - Each
s[i]is a printable ASCII character
Sample 1 · Input
s = ["h","e","l","l","o"]
Output
["o","l","l","e","h"]
Sample 2 · Input
s = ["H","a","n","n","a","h"]
Output
["h","a","n","n","a","H"]
The input is a list of one-character strings, because a Python str cannot be changed after it is made and a list can. Rearranging the list the judge passed in, instead of building a new one, is what the statement means by in place.
Building the reversed string in a second array would take as much extra memory as the input, and the statement allows only . Swapping the mirrored pairs in place needs only the two indices. Put an index left on the first character and an index right on the last, swap the two characters, move both indices one step toward the middle, and repeat while left is less than right:
def reverse_string(s):
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
s = list("hello")
reverse_string(s)
print(s)list("hello") gives the list of characters the problem hands you.
Each swap puts two characters in their final places, so characters take swaps, which is rounded down: 2 swaps for hello and 50,000 for the longest input. When is odd, the indices meet on the middle character, which is already in its place.
Check a palindrome with the same walk
A palindrome is a string that reads the same forwards and backwards, such as racecar or noon. In terms of positions, the two characters of every mirrored pair are equal. So the check is the same walk with a comparison in place of the swap. If the characters at left and right differ, the string is not a palindrome and the check stops. If they are equal, both indices move one step inward. If the indices meet or pass each other and no pair has differed, the string is a palindrome.
racecar all match, and the middle e is never compared. In abca the inner pair differs, so the check stops there.The answer is right because, at each moment of the walk, every mirrored pair outside left and right has been compared and found equal. When the indices meet, the one character left is the middle one, which is its own mirror, and when they pass each other, no character is left. The check makes at most comparisons and does not copy the string.
Worked example
Trace the palindrome check
The trace runs the check on racecar one comparison at a time. The other three inputs are abca, whose inner pair differs; a single letter, where both indices start on the same character and nothing is compared; and abba, which has an even length and so no middle character.
A palindrome reads the same from both ends. Compare only the still-unchecked pair.
Change the example input
Current result: true
Skip the characters that do not count
racecar is a single clean word. A whole sentence can be a palindrome too, if we agree to ignore its spaces, its punctuation and the difference between capital and small letters. The next problem asks for that.
You get a phrase s. Turn every uppercase letter into lowercase and remove every character that is not a letter or a digit. Return true if what remains reads the same forwards and backwards.
Constraints
-
s.length scontains only printable ASCII characters
Sample 1 · Input
s = "A man, a plan, a canal: Panama"
Output
true
Sample 2 · Input
s = "race a car"
Output
false
Sample 3 · Input
s = " "
Output
true
With capital letters changed to lowercase and everything except letters and digits removed, the first sample is amanaplanacanalpanama, a palindrome. The second sample cleans to raceacar, which is not a palindrome: the mirrored pair at indices 3 and 4 is e and a. The third sample is a single space, which cleans to the empty string. The empty string counts as a palindrome because it has no pair that could differ.
One solution is to build that cleaned string and run the palindrome check on it. That works, but it needs a second string as long as the phrase. The walk can do the cleaning as it goes. If the character at left is not a letter or a digit, left moves one step on without a comparison, and right does the same on its side. The two characters are compared, in lowercase, only when both indices rest on a letter or a digit:
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
if not s[left].isalnum():
left += 1
elif not s[right].isalnum():
right -= 1
elif s[left].lower() != s[right].lower():
return False
else:
left += 1
right -= 1
return True
print(is_palindrome("A man, a plan, a canal: Panama"))
print(is_palindrome("race a car"))
print(is_palindrome(" "))isalnum is true for letters and digits, and lower gives the lowercase letter.
The characters the indices step over are the ones the cleaning would have removed, so the pairs that do get compared are the mirrored pairs of the cleaned string. Each pass through the loop moves at least one index a step toward the other, and they start positions apart, so the loop runs fewer than times, under 200,000 for the longest phrase. On the third sample both indices start at 0, the loop body does not run, and the function returns true.
Cut a string into words
Every step so far handled one character. Some problems are about larger pieces of the text, such as the words of a sentence. For those, the first step is to cut the string into its pieces, and the rest of the work happens on a list.
You get a sentence s of words separated by spaces. Return the words in reverse order, joined by single spaces. The input may have spaces at either end and several spaces between words; the output has none of those.
Constraints
-
s.length scontains English letters, digits and spacesshas at least one word
Sample 1 · Input
s = "the sky is blue"
Output
"blue is sky the"
Sample 2 · Input
s = " hello world "
Output
"world hello"
Sample 3 · Input
s = "a good example"
Output
"example good a"
Reversing a list of words is the easy half of this problem. The harder half is the spaces: the second sample has spaces at both ends and the third has three in a row, and none of the extra ones may reach the output.
Python's s.split(), called with no argument, does the cutting. It treats any run of spaces as one separator and ignores spaces at the two ends, so " hello world ".split() is ["hello", "world"]. After the list is reversed, " ".join(words) builds the answer with exactly one space between neighbouring words:
def reverse_words(s):
words = s.split()
words.reverse()
return " ".join(words)
print(reverse_words("the sky is blue"))
print(reverse_words(" hello world "))
print(reverse_words("a good example"))split() with no argument treats any run of spaces as one separator.
Splitting reads each character once and join writes each character once, so the time is proportional to the length of the sentence, which is at most 10,000 characters. The function joins a list because in Python, result += word in a loop can copy everything built so far each time.
Substrings and subsequences
Problem statements use a few fixed words for a piece of a string and for the order of two strings. Whether a statement says substring or subsequence decides which methods can solve it, so check which one it uses:
- A substring is a run of consecutive characters.
bcdis a substring ofabcde. The same thing in a list of numbers is called a subarray. - A subsequence is what you get by deleting zero or more characters of a string without changing the order of the rest, so its characters need not be next to each other.
aceandbcdare both subsequences ofabcde, but onlybcdis a substring. Deleting nothing leaves the whole string and deleting everything leaves the empty string, so both of those are subsequences too. - A prefix is a substring that starts at index 0, such as
abc, and a suffix is one that ends at the last index, such ascde. - Strings are compared in lexicographic order, the dictionary order that
<uses. To compare two strings, find the first index where they differ. The string with the smaller character code at that index comes first. If one string is a prefix of the other, the shorter one comes first. Soappcomes beforeapple, andapplebeforeapply. Capital letters have the codes 65 to 90, below the small letters, soZoocomes beforeapple. One comparison can take as many steps as the shorter string has characters.
abcde, the substring bcd takes three consecutive positions, and the subsequence ace skips indices 1 and 3.A string has far more subsequences than substrings. A string of characters has substrings of length 1, of length 2, and so on down to one of length , which adds up to . A subsequence is fixed by deciding, for each character, whether to keep it, which makes subsequences, or without the empty one. abcde has substrings and subsequences. Both counts treat pieces at different positions as different, even when they spell the same thing. With 30 characters the gap is much wider:
So a program can afford to loop over every start and end of a substring when the string has a few thousand characters: a string of 3,000 has 4,501,500 such pairs. It cannot loop over every subsequence of even a short string: at 25 characters there are already over 33 million. Sliding windows work on substrings, and dynamic programming solves many problems about subsequences.
Common string mistakes
Using 26 counters on text that has capital letters.
- Where it breaks
Zhas code 90, so its index is . In Python,count[-7]iscount[19], and the Z is counted as a t without any error. In C++, the program writes outside the array.- The fix
- Lowercase the text first if the problem treats
Zandzas the same letter. Otherwise use 128 counters indexed by the code itself.
Moving both indices when only one of them is on a character to skip.
- Where it breaks
- In Valid Palindrome on
,ab,leftis on the comma andrightis on b. Moving both puts them on index 1 together, the loop ends, and the function returns true. The cleaned string isab, so the answer is false. - The fix
- Move only the index that is on a character to skip, then test again.
Cutting a sentence at every single space.
- Where it breaks
- Python's
"a b".split(" ")and C++'sgetline(in, word, ' ')both cuta b, which has two spaces, into three pieces:a, an empty string andb. Reversed and joined, they giveb awith two spaces. - The fix
- Use
split()with no argument in Python andin >> wordin C++. Both treat a run of spaces as one separator.
Recall Letter counts cannot tell whether a string is a palindrome: `aab` and `aba` have the same counts. What do the counts tell you about whether a string can be rearranged into one?
In a palindrome, every mirrored pair holds two copies of one letter, so each letter is used an even number of times. The one exception is the middle character of a palindrome of odd length, which uses one copy on its own. So a string can be rearranged into a palindrome exactly when at most one of its letters has an odd count: half the copies of each letter go on the left, the same letters in reverse order on the right, and the letter left over, if there is one, in the middle.
aabbc has counts 2, 2 and 1 and rearranges to abcba. aabc has two letters with an odd count and cannot be rearranged into a palindrome.
Further reading
- Antti Laaksonen (PDF)Competitive Programmer’s Handbook, Chapter 26: String algorithms(opens in a new tab)
Section 26.1, pages 243 and 244, defines substrings, subsequences, prefixes, suffixes, rotations, periods, borders and lexicographic order, with the counts of substrings and subsequences this lesson works out.
- USACO Guide, GeneralData Types(opens in a new tab)
The paragraph on characters shows the arithmetic this lesson uses for its tables: a character is an ASCII integer, so
'f' - 'a'is 5. - Python documentationBuilt-in Types: text sequence type str(opens in a new tab)
Every
strmethod used in this lesson, includingsplit,join,isalnumandlower, with the exact rules for splitting on runs of whitespace. - Python documentationProgramming FAQ: concatenating many strings(opens in a new tab)
Why repeated
+=on a string costs time quadratic in the total length, and the list-and-joinpattern that Reverse Words uses here. - cppreferencestd::basic_string(opens in a new tab)
The mutable C++ string: its member functions such as
findandsubstr, and which operations invalidate references into it. - Joel Spolsky, Joel on SoftwareThe Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets (No Excuses!)(opens in a new tab)
What changes once text leaves plain ASCII, where this lesson’s tables of 128 codes and its one character per position stop holding.
- OI Wiki, in Chinese字符串基础 (String basics)(opens in a new tab)
Definitions of substrings, subsequences, prefixes, suffixes, lexicographic order, palindromes and Hamming distance, and how C and C++ store strings.
- Jeff Erickson (PDF)Algorithms, Chapter 2: Backtracking(opens in a new tab)
Section 2.6 defines subsequences and substrings, then finds the longest increasing subsequence of an array by deciding, for each element in turn, whether to keep it. Parts of this page adapt this chapter’s text, licensed CC BY 4.0 (creativecommons.org/licenses/by/4.0), with changed wording, examples and code.