Introduction to Strings

EditorialUpdated Oct 25, 2026

A string is an array of numbers

Type a message, and every key you press adds one character to the end of a string. A string is just an array of characters, and a character is a small number: in every language here, 'a' is 97, 'b' is 98, and so on up to 'z' at 122. So everything from Introduction to Arrays applies. s[i] is one step away, a walk over the string is O(n), and a running record works on characters as well as on numbers.

Characters being numbers gives you one trick you'll use constantly. c - 'a' (in Python, ord(c) - ord('a')) turns a lowercase letter into a slot from 0 to 25. For 'c' it's 2. An array of 26 counts then does the job of a hash map for letters, with no hashing at all:

def letter_counts(s):
    counts = [0] * 26                           # one slot per letter: 'a' is slot 0, 'z' is slot 25
    for c in s:
        counts[ord(c) - ord('a')] += 1
    return counts

letter_counts('cab') starts [1, 1, 1], one each for a, b and c, and the counts for 'banana' add up to 6.

The string cab as three cells. Under each letter is its code, 99, 97 and 98, then that code minus 97: 2, 0 and 1. Arrows go from those numbers to slots 2, 0 and 1 of a row of 26 counting slots labelled a to z, each of which now holds 1.

Changing and building strings

In C++ a string can change: after t[0] = 'x', "abc" was "xbc". In Java, Python and JavaScript it can't. Python's s[0] = 'b' raised TypeError: 'str' object does not support item assignment. To "change" one of those strings you build a new one.

That's where the cost hides. Building a string one character at a time is fine when each step adds to the end of a buffer with room to spare, the way a dynamic array appends. It's O(n²) when each step makes a whole new string and copies everything before it: 1 + 2 + … + n characters.

Building hello one letter at a time, two ways. Left: each step makes a new string, copies the letters so far and writes the new one: 0, 1, 2, 3 and 4 letters copied, 10 copies and 5 writes in all. Right: a buffer with spare room, where each step writes one letter and nothing is copied, 5 writes.

Which ways copy depends on the language and on how you write it. Here are 100,000 characters added one at a time, timed on the judge:

Language	Copies every time	Adds in place
C++	`q = q + c`: 0.61 s	`s += c`: 0.4 ms
Python	`p = c + p` (adding at the front): 0.21 s	`''.join(parts)`: 9.9 ms
Java	`s += c`: 0.77 s	`StringBuilder.append`: 3.5 ms
JavaScript	neither is slow here: `p = c + p` took 6.9 ms	`s += c`: 12.7 ms

Two surprises. Python's s += c took only 18.5 ms: CPython quietly grows the string in place when nothing else is holding it. That's an implementation detail, not a promise, and it doesn't apply to adding at the front. And JavaScript engines store a sum of strings as a rope, a tree of pieces, so + is cheap until something reads the characters.

The habit that's right in every language: collect the pieces in a buffer, and join once at the end. Reverse Words in a String shows each language's way. Return the words in reverse order, with one space between them and none at the ends, whatever spaces the input had:

string reverseWords(const string& s) {
    vector<string> words;
    string word;
    for (char c : s) {                               // collect the words, skipping every run of spaces
        if (c != ' ') word += c;                     // += appends in place
        else if (!word.empty()) { words.push_back(word); word.clear(); }
    }
    if (!word.empty()) words.push_back(word);
    string out;
    for (int i = (int)words.size() - 1; i >= 0; i--) {
        out += words[i];
        if (i > 0) out += ' ';
    }
    return out;
}

def reverse_words(s):
    words = s.split()                           # split() with no argument drops every run of spaces
    return " ".join(reversed(words))            # one join builds the result in O(n)

static String reverseWords(String s) {
    String[] words = s.trim().split("\\s+");         // trim the ends, then split on runs of spaces
    StringBuilder out = new StringBuilder();         // a buffer: += on a String would copy it every time
    for (int i = words.length - 1; i >= 0; i--) {
        out.append(words[i]);
        if (i > 0) out.append(' ');
    }
    return out.toString();
}

function reverseWords(s) {
    return s.trim().split(/\s+/).reverse().join(' ');   // trim, split on runs of spaces, reverse, join once
}

Each prints [blue is sky the], [world hello], [example good a] and [x] for "the sky is blue", " hello world ", "a good example" and "x" (the brackets show the ends). O(n) time and O(n) space in every version.

Counting characters

With 26 counts you can answer most "how many of each letter" questions in one pass. Sort Characters By Frequency counts, then writes each character as many times as it appeared, most frequent first. Sum of Beauty of All Substrings needs the counts of every substring. Grow the counts one letter at a time from each start, instead of recounting each substring, and each step costs O(26):

def beauty_sum(s):
    total = 0
    for start in range(len(s)):
        counts = [0] * 26                       # the counts of s[start..end], grown one letter at a time
        for end in range(start, len(s)):
            counts[ord(s[end]) - ord('a')] += 1
            present = [k for k in counts if k]
            total += max(present) - min(present)
    return total

It returned 5 for 'aabcb' and 17 for 'aabcbaa'. Each substring's beauty is its most common count minus its least common one. There are about n²/2 substrings, so it's O(26 · n²), which is fine for the problem's n ≤ 500. Recounting each substring from scratch would make it O(n³).

When the characters aren't just lowercase letters, use 128 slots (ASCII) or a hash map (the Hashing section).

Comparing and searching

Strings compare character by character, by code, so the order is "dictionary order" only for one case. Uppercase letters (65 to 90) come before lowercase ones (97 to 122): "Zebra" < "apple" was true in Java and Python.

Longest Common Prefix compares column by column: the prefix grows while every string has the same character at position i. Check each string's length before reading it:

def longest_common_prefix(strs):
    first = strs[0]
    for i, c in enumerate(first):               # column by column, while every string agrees
        for s in strs[1:]:
            if i == len(s) or s[i] != c:        # check the length first: a shorter string ends the prefix
                return first[:i]
    return first

It returned fl, '' and a for ['flower', 'flow', 'flight'], ['dog', 'racecar', 'car'] and ['ab', 'a'].

Rotate String asks whether s can be turned into goal by moving letters from the front to the back. Write s twice: every rotation of s is a window of s + s. "cdeab" sits inside "abcdeabcde", starting at 2.

def rotate_string(s, goal):
    return len(s) == len(goal) and goal in s + s   # every rotation of s sits inside s + s

It returned True for ('abcde', 'cdeab') and False for ('abcde', 'abced').

Searching for a substring. Find the Index of the First Occurrence in a String is the search the direct way. Try each start where the needle still fits, and compare it character by character until a mismatch or a full match:

Finding "abc" in "abababc" — The haystack on top, the needle below. Green characters have matched at the current start; the indigo pair is being compared, and an amber pair doesn't match.

int strStr(const string& haystack, const string& needle) {
    int n = haystack.size(), m = needle.size();
    for (int start = 0; start + m <= n; start++) {   // every start where the needle still fits, the last too
        int j = 0;
        while (j < m && haystack[start + j] == needle[j]) j++;
        if (j == m) return start;                    // the whole needle matched here
    }
    return -1;
}

def str_str(haystack, needle):
    n, m = len(haystack), len(needle)
    for start in range(n - m + 1):              # every start where the needle still fits, the last too
        j = 0
        while j < m and haystack[start + j] == needle[j]:
            j += 1
        if j == m:                              # the whole needle matched here
            return start
    return -1

static int strStr(String haystack, String needle) {
    int n = haystack.length(), m = needle.length();
    for (int start = 0; start + m <= n; start++) {   // every start where the needle still fits, the last too
        int j = 0;
        while (j < m && haystack.charAt(start + j) == needle.charAt(j)) j++;
        if (j == m) return start;                    // the whole needle matched here
    }
    return -1;
}

function strStr(haystack, needle) {
    const n = haystack.length, m = needle.length;
    for (let start = 0; start + m <= n; start++) {   // every start where the needle still fits, the last too
        let j = 0;
        while (j < m && haystack[start + j] === needle[j]) j++;
        if (j === m) return start;                   // the whole needle matched here
    }
    return -1;
}

Each prints 0, -1, 4, 2, 0 and -1 for ("sadbutsad", "sad"), ("leetcode", "leeto"), ("abababc", "abc"), ("abc", "c"), ("a", "a") and ("ab", "abc"). The step-through made 11 comparisons. In the worst case each of the n − m + 1 starts compares up to m characters: O((n − m + 1) · m). For a 100,000-character haystack and a 1,000-character needle that's up to 99,001,000 comparisons. The Advanced String Algorithms section gets it down to O(n + m), with KMP and rolling hashes.

Strings in your language

What each language lets you do with a string, and how to compare two. All of these ran on the judge.

Language	Change one character	Build a string with	Compare with
C++	yes: `s[0] = 'x'`	`s += c`	`==`
Python	no: `s[0] = 'b'` raises `TypeError`	a list, then `''.join`	`==`
Java	no; read one with `s.charAt(i)`	`StringBuilder`	`.equals`, never `==`
JavaScript	no, and `s[0] = 'x'` is ignored with no error	an array, then `join`	`===`

And the trap in each:

C++: s = s + c builds a whole new string first: the slow C++ row in Changing and building strings. Pass strings as const string&, so a call doesn't copy them.
Python: s.split(" ") splits on every single space: " hello world ".split(" ") gave ['', '', 'hello', '', '', 'world', '', '']. s.split() with no argument splits on any run of spaces and drops the empty pieces.
Java: == compares whether two variables point to the same object, not the characters: "ab" == new String("ab") was false, and .equals was true.
JavaScript: length counts UTF-16 units, not characters: "😀".length was 2, and [..."😀"].length was 1. For plain letters, digits and spaces they agree.

Spotting it

Most string problems are array problems with characters. Clues and what they usually mean:

"lowercase English letters": an array of 26 counts, indexed by c - 'a'.
building or changing a string inside a loop: a buffer (StringBuilder, a list, an array) and one join.
"rotation", "cyclic shift": look inside s + s.
"words", "spaces": split carefully (repeated spaces, the ends), or walk the characters yourself.
"find a pattern", once: the direct search is fine when the strings are small.

And the near-misses:

many searches, or long patterns: the direct search's O(n · m) is too slow. Use KMP or a rolling hash (Advanced String Algorithms).
substrings that read the same both ways: expand around centers, in Palindromes: Expand Around the Center.
the longest substring with some property: usually a sliding window (Sliding Window).

Common mistakes

Adding to a Java String in a loop. s += c

Every += copies the whole string: 100,000 characters took 0.77 s, against 3.5 ms with a StringBuilder.

Comparing Java strings with ==.

"ab" == new String("ab") was false. Use .equals.

Stopping the search one start too early. for start in range(n - m)

The last start, n − m, is never tried, so str_str("abc", "c") returned -1. The answer is 2. Loop to n − m inclusive: range(n - m + 1).

Splitting on a single space. s.split(" ")

Reversing the words of " hello world " gave [ world hello ] (brackets show the ends): the empty pieces between spaces became words. Use split(), or trim and split on runs of spaces.

Indexing past a shorter string. if s[i] != c: without i == len(s)

Longest Common Prefix on ['ab', 'a'] raised IndexError: string index out of range. Check the length first.

Check yourself

Quiz

1 / 6

Multiple choice

In Python, what is ord('e') - ord('a')?

Practice problems

From easier to harder:

Largest Odd Number in String: scan from the right for the last odd digit.
Length of Last Word: walk back from the end, past the spaces.
Longest Common Prefix: column by column, lengths first.
Rotate String: look inside s + s.
Find the Index of the First Occurrence in a String: the direct search, every start.
Reverse Words in a String: split on runs of spaces, join once.
Sort Characters By Frequency: count, then write the most frequent first.
Sum of Beauty of All Substrings: counts grown one letter at a time.

Next: Parsing Strings in One Pass.