Data structure 2 of 12

Strings and characters

A string is an array of characters with one twist: you can't change it. Every "change" makes a new string, so the way you build text decides whether your solution is fast or quietly quadratic.

A 3-minute conversation: Sam asks, Priya explains

0:00 / 2:33

Follow along on the page Pause on “your turn” questions

Sam Strings next. Aren't they just arrays of letters?
Priya With one twist: you can't change them. Every change makes a new string. So how you build text decides whether your solution is fast or quietly quadratic.
Priya Picture letter tiles glued to a strip of card. You can read any tile instantly, but you can't swap one. To change the word you lay out a new strip. Smart builders collect loose tiles in a tray first, then glue once.
Sam And characters are numbers?
Priya Each one is stored as a code. Lowercase a is ninety-seven, b is ninety-eight. So ord of c minus ord of a turns a lowercase letter into a slot from zero to twenty-five.
Sam Why is adding a letter in a loop slow?
Priya Because the string can't grow. Plus-equals builds a brand new string and copies everything so far. Over n letters that's one plus two plus three, all the way to n copies: quadratic. Append to a list instead, and join once at the end.
Sam The costs, then.
Priya Reading a character and the length are constant. A slice copies its characters. Joining two strings copies both. Searching for a substring can be slow. And comparing goes letter by letter until they differ.
Priya Your turn. You're building a long result string piece by piece. What's the fast way in Python?
Priya Append the pieces to a list and join once. In Java, a StringBuilder.
Sam Language traps?
Priya In Java, compare strings with dot equals, never double equals. And in JavaScript, assigning to one character silently does nothing.
Sam The four players?
Priya Walk the characters and count letters and digits. Build a new string with a list and join, reversing the words of a sentence. Letters as numbers: twenty-six jars, one per letter. And comparing from both ends to check a palindrome.
Sam Memory hook?
Priya Glued tiles. Read freely, build in a list, join once. And every tile is secretly a number.
Sam Problems?
Priya Merge strings alternately, building with a list. Length of last word, walking backwards from the end. And first unique character, counting letters in twenty-six slots, then scanning again in order.
Sam Mistakes?
Priya Plus-equals in a loop. Trying to change a character. Assuming only lowercase letters when the input has capitals. And splitting on a single space when there might be several.
Sam Next?
Priya Lesson three, hash maps: the tool that turns "search for it" into "look it up".

1. What it is

A word spelled out in letter tiles glued to a strip of card. You can read any tile instantly by its position, but you can't swap a tile: to change the word you lay out a new strip. Smart builders collect loose tiles in a tray first and glue the whole strip once.

A string is a sequence of characters, indexed from 0 like an array. Each character is stored as a number, its character code ('a' is 97, 'b' is 98, 'A' is 65, '0' is 48). In Python, TypeScript and Java strings are immutable: once made, they never change.

Reading s[i] and len(s) are O(1), like an array.
Changing means building a new string. Doing that one character at a time in a loop copies the text again and again.
Letters are numbers, so ord(c) − ord('a') turns a lowercase letter into a slot from 0 to 25.

2. How it sits in memory

Each character occupies one slot holding its code. That is why you can index a string, compare letters with <, and do arithmetic on them.

Because a string can't change, s += c builds a brand-new string and copies everything so far. In a loop of n characters that is 1 + 2 + … + n copies, which is O(n²). Collecting characters in a list (which can grow) and joining once is O(n).

3. Operations and what they cost

Operation	Python	Cost	Why
Read character i, length	`s[i]`, `len(s)`	`O(1)`	Same as an array.
Slice	`s[a:b]`	`O(b − a)`	Copies the characters into a new string.
Join two strings	`s + t`	`O(len s + len t)`	A new string holding both.
Append in a loop	`s += c` n times	`O(n²)` total	Each step copies everything so far.
Build from pieces	`"".join(parts)`	`O(total length)`	One copy at the end.
Find a substring	`t in s`, `s.find(t)`	up to `O(len s × len t)`	Tries each starting position.
Compare	`s == t`, `s < t`	`O(n)`	Character by character until they differ.
Letter ↔ code	`ord(c)`, `chr(n)`	`O(1)`	A lookup.

Rule of thumbBuilding a string piece by piece? Append to a list (Python, TypeScript) or a StringBuilder (Java), then join once.

4. In Python, TypeScript and Java

Everyday string work in each language.

s = "level up"
    first = s[0]                 # 'l'
    size = len(s)                # 8
    words = s.split()            # ['level', 'up']
    shout = s.upper()            # 'LEVEL UP'
    code = ord("a")              # 97
    letter = chr(98)             # 'b'
    slot = ord("d") - ord("a")   # 3, a slot in a 26-letter array
    parts = []
    for c in "abc":
        parts.append(c.upper())
    built = "".join(parts)       # 'ABC', built in O(n)

const s = "level up";
    const first = s[0];                       // "l"
    const size = s.length;                    // 8
    const words = s.split(" ");               // ["level", "up"]
    const shout = s.toUpperCase();            // "LEVEL UP"
    const code = "a".charCodeAt(0);           // 97
    const letter = String.fromCharCode(98);   // "b"
    const slot = "d".charCodeAt(0) - "a".charCodeAt(0);  // 3
    const parts: string[] = [];
    for (const c of "abc") parts.push(c.toUpperCase());
    const built = parts.join("");             // "ABC"

String s = "level up";
    char first = s.charAt(0);                 // 'l'
    int size = s.length();                    // 8
    String[] words = s.split(" ");            // ["level", "up"]
    String shout = s.toUpperCase();           // "LEVEL UP"
    int code = 'a';                           // 97: a char is a number
    char letter = (char) 98;                  // 'b'
    int slot = 'd' - 'a';                     // 3
    StringBuilder sb = new StringBuilder();
    for (char c : "abc".toCharArray()) sb.append(Character.toUpperCase(c));
    String built = sb.toString();             // "ABC"

5. Core operations, step by step

Four string skills that come up constantly. Press Play on any player to hear each step explained.

A · Walk the characters (count letters and digits)

What it doesVisits each character once and classifies it.

Picture itReading the tiles left to right with two tally counters in your hands.

CostO(n) time, O(1) space.

The code. A plain loop over the characters; the language tells you what kind each one is.

def count_kinds(s):
    letters = digits = 0
    for c in s:
        if c.isalpha():
            letters += 1
        elif c.isdigit():
            digits += 1
    return letters, digits

function countKinds(s: string): [number, number] {
  let letters = 0, digits = 0;
  for (const c of s) {
    if (/[a-zA-Z]/.test(c)) {
      letters += 1;
    } else if (/[0-9]/.test(c)) {
      digits += 1;
    }
  }
  return [letters, digits];
}

static int[] countKinds(String s) {
    int letters = 0, digits = 0;
    for (char c : s.toCharArray()) {
        if (Character.isLetter(c)) {
            letters += 1;
        } else if (Character.isDigit(c)) {
            digits += 1;
        }
    }
    return new int[]{letters, digits};
}

Line by line.

Line	What it does	Why
`for c in s`	One character at a time.	No index needed when you only read.
`if c.isalpha()`	Is it a letter?	Built-in checks beat comparing against long lists of characters.
`elif c.isdigit()`	Otherwise, is it a digit?	Anything else (spaces, punctuation) is ignored.

Watch it run. Classify "a1b2c!".

Watch out for:

Indexing when you don't need to. for c in s is clearer than for i in range(len(s)) when the index isn't used.

B · Build a new string with a list and join

What it doesCollects pieces in a growable list, then glues them once.

Picture itCollect loose tiles in a tray, then glue the strip once.

CostO(n) time and space, instead of O(n²) for repeated +=.

The code. Reverse the words of a sentence by collecting them in a list.

def reverse_words(s):
    parts = []
    for word in s.split():
        parts.append(word)
    parts.reverse()
    return " ".join(parts)

function reverseWords(s: string): string {
  const parts: string[] = [];
  for (const word of s.split(" ").filter((w) => w)) {
    parts.push(word);
  }
  parts.reverse();
  return parts.join(" ");
}

static String reverseWords(String s) {
    List<String> parts = new ArrayList<>();
    for (String word : s.trim().split("\\s+")) {
        parts.add(word);
    }
    Collections.reverse(parts);
    return String.join(" ", parts);
}

Line by line.

Line	What it does	Why
`parts = []`	A tray for the pieces.	A list can grow cheaply; a string can't.
`parts.append(word)`	Add one piece.	O(1): no copying of earlier words.
`return " ".join(parts)`	Glue everything once.	One pass over all the characters.

Watch it run. Reverse the words of "practice makes progress".

Watch out for:

result = result + word in a loop. Each step copies everything so far: O(n²). Use a list or StringBuilder.

C · Letters as numbers (a 26-slot count)

What it doesTurns each lowercase letter into a slot 0–25 with ord(c) − ord('a') and counts it.

Picture itA row of 26 jars labelled a to z. Each tile drops into its own jar.

CostO(n) time, O(1) space (always 26 slots).

The code. An array of 26 counters is a lighter alternative to a hash map when the alphabet is fixed.

def letter_counts(s):
    counts = [0] * 26
    for c in s:
        slot = ord(c) - ord("a")
        counts[slot] += 1
    return counts

function letterCounts(s: string): number[] {
  const counts = new Array(26).fill(0);
  for (const c of s) {
    const slot = c.charCodeAt(0) - "a".charCodeAt(0);
    counts[slot] += 1;
  }
  return counts;
}

static int[] letterCounts(String s) {
    int[] counts = new int[26];
    for (char c : s.toCharArray()) {
        int slot = c - 'a';
        counts[slot] += 1;
    }
    return counts;
}

Line by line.

Line	What it does	Why
`counts = [0] * 26`	One counter per letter.	Fixed size: O(1) space whatever the input.
`slot = ord(c) - ord("a")`	'a' → 0, 'b' → 1, … 'z' → 25.	Codes of a to z are consecutive.
`counts[slot] += 1`	Drop the tile in its jar.	Array indexing is O(1).

Watch it run. Count the letters of "banana".

Watch out for:

Using it for uppercase or other characters. Only lowercase a–z fit slots 0–25. Lower-case first, or use a hash map for anything wider.

D · Compare from both ends (is it a palindrome?)

What it doesChecks the first and last characters, then moves both inwards.

Picture itTwo friends read the same word, one from each end, and shout if their letters ever differ.

CostO(n) time, O(1) space.

The code. Two indices walking towards each other; strings are read-only, so nothing is copied.

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

function isPalindrome(s: string): boolean {
  let left = 0, right = s.length - 1;
  while (left < right) {
    if (s[left] !== s[right]) {
      return false;
    }
    left += 1;
    right -= 1;
  }
  return true;
}

static boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left += 1;
        right -= 1;
    }
    return true;
}

Line by line.

Line	What it does	Why
`left, right = 0, len(s) - 1`	Start at both ends.	The last index is len − 1.
`while left < right`	Stop when they meet.	The middle character of an odd word needs no partner.
`if s[left] != s[right]`	Do the mirrored letters match?	One mismatch decides it.

Watch it run. Check "racecar".

Watch out for:

s == s[::-1] in an interview. Correct, but it copies the string (O(n) extra space). Know the two-index version too.

6. How to remember it

Memory hook: "Glued tiles"Read any tile instantly, but never re-glue one: lay new tiles in a tray and glue the strip once. And every tile is secretly a number.

Picture

Letter tiles on a strip of card, each with its code (97, 98 …) printed underneath.

Chant

"Read freely, build in a list, join once."

Key rule

ord(c) − ord('a') turns a lowercase letter into a slot 0–25.

7. Problems solved with it

Three easy problems, one for each core skill: building, walking and counting.

LC 1768 · Merge Strings Alternately

The problemMerge word1 and word2 by taking letters in turn, starting with word1. Add whatever is left of the longer word at the end.

What it doesTakes one letter from each word in turn into a list, then joins.

CostO(n + m).

The code. One index walks both words; a list collects the letters.

def merge_alternately(word1, word2):
    parts = []
    for i in range(max(len(word1), len(word2))):
        if i < len(word1):
            parts.append(word1[i])
        if i < len(word2):
            parts.append(word2[i])
    return "".join(parts)

function mergeAlternately(word1: string, word2: string): string {
  const parts: string[] = [];
  for (let i = 0; i < Math.max(word1.length, word2.length); i++) {
    if (i < word1.length) {
      parts.push(word1[i]);
    }
    if (i < word2.length) {
      parts.push(word2[i]);
    }
  }
  return parts.join("");
}

static String mergeAlternately(String word1, String word2) {
    StringBuilder parts = new StringBuilder();
    for (int i = 0; i < Math.max(word1.length(), word2.length()); i++) {
        if (i < word1.length()) {
            parts.append(word1.charAt(i));
        }
        if (i < word2.length()) {
            parts.append(word2.charAt(i));
        }
    }
    return parts.toString();
}

Line by line.

Line	What it does	Why
`for i in range(max(len(word1), len(word2)))`	Enough turns for the longer word.	The shorter word simply runs out.
`if i < len(word1)`	Does word1 still have a letter here?	Prevents reading past its end.
`return "".join(parts)`	Glue once.	O(total length).

Watch it run. "abc" and "pqrst".

Watch out for:

Stopping at the shorter length. The rest of the longer word would be lost.

LC 58 · Length of Last Word

The problemReturn the length of the last word in s. Words are separated by spaces, and s may end with spaces.

What it doesWalks from the end: skips trailing spaces, then counts letters until a space.

CostO(n) time, O(1) space.

The code. Read the tiles backwards; no splitting or copying.

def length_of_last_word(s):
    i = len(s) - 1
    while i >= 0 and s[i] == " ":
        i -= 1
    length = 0
    while i >= 0 and s[i] != " ":
        length += 1
        i -= 1
    return length

function lengthOfLastWord(s: string): number {
  let i = s.length - 1;
  while (i >= 0 && s[i] === " ") {
    i -= 1;
  }
  let length = 0;
  while (i >= 0 && s[i] !== " ") {
    length += 1;
    i -= 1;
  }
  return length;
}

static int lengthOfLastWord(String s) {
    int i = s.length() - 1;
    while (i >= 0 && s.charAt(i) == ' ') {
        i -= 1;
    }
    int length = 0;
    while (i >= 0 && s.charAt(i) != ' ') {
        length += 1;
        i -= 1;
    }
    return length;
}

Line by line.

Line	What it does	Why
`while i >= 0 and s[i] == " "`	Skip spaces at the end.	Trailing spaces aren't part of any word.
`while i >= 0 and s[i] != " "`	Count letters until a space.	i >= 0 first: never read s[-1] by accident.

Watch it run. "fly me to the moon ".

Watch out for:

s.split()[-1] without thinking. Fine in Python, but it builds a list of every word. The backwards walk uses O(1) space.

LC 387 · First Unique Character in a String

The problemReturn the index of the first character that appears exactly once in s (lowercase letters only), or −1.

What it doesCounts letters in 26 slots, then finds the first letter whose count is 1.

CostO(n) time, O(1) space.

The code. Two passes: count everything, then look again in order.

def first_uniq_char(s):
    counts = [0] * 26
    for c in s:
        counts[ord(c) - ord("a")] += 1
    for i, c in enumerate(s):
        if counts[ord(c) - ord("a")] == 1:
            return i
    return -1

function firstUniqChar(s: string): number {
  const counts = new Array(26).fill(0);
  for (const c of s) {
    counts[c.charCodeAt(0) - 97] += 1;
  }
  for (let i = 0; i < s.length; i++) {
    if (counts[s.charCodeAt(i) - 97] === 1) {
      return i;
    }
  }
  return -1;
}

static int firstUniqChar(String s) {
    int[] counts = new int[26];
    for (char c : s.toCharArray()) {
        counts[c - 'a'] += 1;
    }
    for (int i = 0; i < s.length(); i++) {
        if (counts[s.charAt(i) - 'a'] == 1) {
            return i;
        }
    }
    return -1;
}

Line by line.

Line	What it does	Why
`for c in s: counts[...] += 1`	First pass: count every letter.	You can't know a letter is unique until you've seen the whole string.
`for i, c in enumerate(s)`	Second pass, in the original order.	Order matters: we want the first unique one.
`if counts[...] == 1`	Exactly once?

Watch it run. "loveleetcode".

Watch out for:

Scanning the counts array for the first 1. That finds the alphabetically first unique letter, not the first in the string.

More practice, solved on the pattern pages

#	Problem	Level	Where
344	Reverse String	Easy	Solved step by step on 02 · Two Pointers
392	Is Subsequence	Easy	Solved step by step on 02 · Two Pointers
14	Longest Common Prefix	Easy	Solved step by step on 21 · Array & String Basics
28	Find the Index of the First Occurrence in a String	Easy	Solved step by step on 21 · Array & String Basics
13	Roman to Integer	Easy	Solved step by step on 21 · Array & String Basics
242	Valid Anagram	Easy	Solved step by step on 16 · Hash Map & Set

8. Common mistakes

Building with += in a loopEach step copies the whole string so far: O(n²). Append pieces to a list (or a Java StringBuilder) and join once.

Trying to change a characters[0] = "x" is an error in Python and silently does nothing in TypeScript. Convert to a list, change it, and join.

Comparing strings with == in Java== checks whether two variables point to the same object. Use s.equals(t).

Assuming lowercase a–zThe 26-slot trick breaks on capitals, digits or other alphabets. Check the constraints, lower-case first, or use a hash map.

Splitting on one space"a b".split(" ") gives an empty word in the middle. Python's split() with no argument handles runs of spaces.

9. Self-check quiz

Building a string of n characters with s += c in a loop costs…

Strings can't grow in place, so step k copies k characters: 1 + 2 + … + n.

What is ord("d") − ord("a")?

The codes of a, b, c, d are consecutive (97 to 100), so d is three slots after a.

You need to build a long result string. What is the fast way in Python?

A list grows cheaply; join copies the characters a single time.

In Java, which checks that two strings hold the same letters?

== compares object identity; two equal strings can be different objects.

10. Where it shows up next

Strings appear in almost every pattern. The closest follow-ups:

21 · Array & String Basics: scanning text with lookups (Roman numerals, zigzag, reversing words).
03 · Sliding Window: the longest substring with some property.
16 · Hash Map & Set: counting letters when the alphabet isn't fixed, and grouping anagrams.
19 · Trie: a tree of letters for prefix searches.

Next structure: 03 · Hash maps, the tool that turns "search for it" into "look it up".