The String

The array in the previous chapter is a row of whiteboard cells: to change one, you erase it and write again. A string is a row of characters carved into stone. Each character still has its own slot, numbered from 0, exactly like an array. But once carved, the slot cannot be rewritten. To turn "rain tomorrow" into "sun tomorrow" you carve a new stone and copy over the parts that did not change as well.

This rule is called immutability. It holds for Java String, Python str, and JavaScript strings alike. It is a deliberate design, not a defect, and the story card below explains why. What matters first is the consequence: every operation that appears to modify a string, whether concatenation, replacement, or a case change, actually copies the whole text. That single fact decides half the complexity results in this chapter.

One more thing to settle up front: the slots do not really hold characters. A computer only stores numbers. A character is what you see after a number is looked up in a character encoding: 65 shows as 'A', and 23383 shows as 字. Three rules follow.

In 1963 ASCII gave the numbers 0 to 127 to the English letters, the digits, the punctuation, and a set of control codes. One character, one byte, and everything worked, as long as you only wrote English. Chinese has tens of thousands of characters and does not fit in 128 numbers, so each region built its own table (GB2312, Big5, Shift-JIS, and others). The same bytes opened in another country produced unreadable text. That is where the old problem of garbled characters comes from.

Unicode solves it in one move: put every character in the world into one list and give each a unique number, called a code point, written U+XXXX. 'A' is U+0041, 字 is U+5B57, and 🙂 is U+1F642. More than 150,000 code points have been assigned. But a code point is only a number. How that number is stored as bytes is a separate question, and that is the job of UTF-8, UTF-16, and UTF-32. Here is the single character 字 at every level.

UTF-8 became the standard on the web because it is variable length: common characters get short encodings, rare ones get long encodings, and plain English text stored as UTF-8 is byte for byte identical to ASCII from 1963. The length is chosen from the code point in four bands.

The three languages index strings differently, and that decides what "length" means. Java and JavaScript index by UTF-16 code unit, so length counts 16-bit units. Python 3 str is a sequence of code points, so len counts code points. Note that a code point is still not always one visible character: an accented letter written as a base letter plus a combining mark is two code points, and a family emoji is several. The difference is invisible in plain English text and shows up the moment an emoji appears. Check it yourself below.

The row worth studying is concatenation. A single s + t is O(n+m), which sounds acceptable. The real problem is += inside a loop. Suppose you build a string of length n one character at a time.

The first += copies 1 character. The second copies 2, the old one plus the new one. The third copies 3. At step i the old string already has i−1 characters and all of them are copied again before the new one is added. The total is 1 + 2 + 3 + … + n = n(n+1)/2 ≈ n²/2. At n = 100,000 that is about 5 billion character copies. Each step looks harmless; the sum is not. This is the arithmetic-series trap: += on an immutable string inside a loop is O(n²).

The fix is a mutable stand-in: append into a mutable container, then build the string once at the end. The total returns to O(n). Watch the two strategies race.

First: a string builder. It works exactly like the dynamic array from the previous chapter. Inside is a mutable character array. append writes into a free slot, which is amortized O(1), and when the array is full the capacity doubles and the contents move once. Only at the end does build copy everything into an immutable string. Reading this makes it clear why collecting first and building once is O(n).

Second: naive substring search (indexOf). Find a pattern of length m inside a text of length n. Try each starting position, and on a mismatch move the start one step right and compare from the beginning again. The idea is direct, and the worst case is O(n·m).

The idea: KMP, where a failure is information. Where does the naive method lose time? Look at one typical failure. Search for ABABC inside the text ABABABC. The first four characters ABAB match and the fifth does not. The naive reaction is to move the start one step right and forget everything, comparing from the beginning again. But we already know that those four characters of the text are ABAB. That knowledge is thrown away.

The whole secret of KMP (Knuth–Morris–Pratt) is that one slide. When the comparison fails, the end of the part that already matched, ABAB, and the start of the pattern share a longest overlap, AB. Slide the pattern until that overlap lines up. The overlapping characters need no recheck, because they were just compared and are known to be equal, so the comparison resumes at the overlap length. The pointer into the text therefore never moves backwards, and the whole search is O(n + m).

"How long is the overlap between the start and the end of each prefix" can be computed in advance from the pattern alone and stored in an array. That array is the prefix function, written next or lps. Its definition is exact: next[i] is the length of the longest proper prefix of pattern[0..i] that is also a suffix of pattern[0..i]. "Proper" means it cannot be the whole of pattern[0..i], otherwise the answer would always be i+1. Here it is for ABABC.

Matching then follows one rule: when the comparison fails at j, set j to next[j−1] and try again; only when j is already 0 does the text pointer move forward. Why does this never skip a valid match? Because next gives the longest overlap, and every shorter alignment is reached by applying the rule again. If the first jump still fails, jump again, following the chain down to 0. The full implementation is below. The code that builds next looks almost the same as the code that matches, because building next is the pattern matching against itself.

In all three languages strings are immutable, indexable, iterable, and rebuilt on every concatenation, so at the level of ideas they agree. What differs is the habits. Java has a string pool and the == trap. Python turns "collect, then join" into muscle memory. JavaScript has the most convenient template literals and the deepest UTF-16 emoji trap.

String techniques overlap heavily with array techniques, which is no surprise given how close the two structures are, but three of them belong here. Read the problem and look for the signal. Palindrome or reversal points to two pointers moving toward each other. The best contiguous substring points to a sliding window. Anagrams or character counts point to a counting array. These three cover most of the problem set in this chapter.

The problem: considering only letters and digits and ignoring case, decide whether the string reads the same forwards and backwards. Brute force: build a filtered lowercase string, then compare it with its reverse. That is correct but builds two new strings of size O(n). Better: two pointers decide it in place, with no new string at all.

The problem: find the length of the longest contiguous substring with no repeated character. Brute force: enumerate every start and end and check each substring for a repeat, O(n³), or O(n²) with a Set. Better: the two sliding-window signals are both present, contiguous and incrementally maintainable. The key insight: while the window [l..r] has no repeat, a new duplicate only requires dropping characters from the left, and l never has to move back, because any earlier start still contains the duplicate that was just removed.

The problem: find the longest contiguous substring that is a palindrome. Note that you have to find it, not just check one. Brute force: enumerate all O(n²) substrings and spend O(n) checking each, giving O(n³). Better: change what you enumerate. Instead of substrings, enumerate the centers. A palindrome has a useful property: remove one character from each end and it is still a palindrome. Read backwards, that says you can grow outward from a center until the two sides disagree, and that is the longest palindrome at this center. There are only 2n−1 centers, n characters plus n−1 gaps.