Skip to content

Strings

Lesson 3 of 7 in Foundations · 30 min · Beginner

An array of characters with its own tricks.

Introduction

A signup form must decide that "Racecar!" and "race car" are both the same word backwards. How can it check that without first building cleaned-up copies of the text?

Capital letters, spaces and punctuation don't count. The obvious plan is to filter out the junk, lower-case what is left, reverse it and compare. That works, but it allocates new strings just to answer yes or no.

Now put one finger on the first character and another on the last. What would you do each time a finger lands on a space or an exclamation mark?

Lesson overview

This lesson will show you how to:

  • Explain why a string behaves like an array of characters.
  • Trace a two-pointer palindrome check that skips punctuation and case.
  • Compare two words by counting letters to spot anagrams.
  • Build a changed string once, instead of editing it character by character.
  • Choose a sliding window instead when the question asks for a longest stretch.

The picture

sR0a1c2e3␣4c5a6r7!8leftrightR equals r, ignoring casespaces are skippedso is punctuationArray s with 9 slots: R, a, c, e, ␣, c, a, r, !. Pointers: left at index 0; right at index 7. Marked: index 0 compare; index 4 discarded; index 7 compare; index 8 discarded.

Mental model

Picture a row of letter tiles on a shelf, one per slot and numbered from 0, so you can reach any tile instantly or walk in from both ends. In Python and Java the tiles are glued down: to change one letter you lay out a whole new row. So you collect tiles on a tray and glue the finished row once.

A string is an array of characters, so every array trick works on text. The one twist is that you usually can't edit it in place.

Words to know

character
One symbol in the string: a letter, digit, space or punctuation mark. In the pictures each character gets its own cell, and a space is drawn as ␣.
immutable
Can't be changed after it is made. Python and Java strings are immutable, so "editing" one builds a new string. C++ std::string is mutable and can be changed in place.
code point
The number a character is stored as. In ASCII 'a' is 97, 'b' is 98 and 'A' is 65. Unicode extends the same idea to every alphabet. This lesson sticks to plain ASCII.
substring
A run of characters that sit side by side, like "car" inside "race car". A subsequence may skip characters but keeps their order, like "rcr".
StringBuilder / join
The way to build a long string efficiently. Java's StringBuilder and Python's ''.join(list) gather the pieces first and make one string at the end.
frequency map
A table of how many times each character appears. It can be a hash map, or for lowercase letters a 26-slot array indexed by ch - 'a'.
anagram
A word made from the same letters as another, used the same number of times, in any order: "listen" and "silent".

Watch it run

Step with → or Next. When a question pops up, make your guess. Try your own input once the guided run ends.

Getting the demo ready…

Recognise it

Most of the skill is noticing the clue in the problem statement.

Reach for it when

  • Yes: The input is text and the question is about its letters, their order or their symmetry.
  • Yes: Two words may be rearrangements of each other, so you need to compare how often each letter appears.
  • Yes: You must compare a string with itself backwards, or work from both ends toward the middle.
  • Yes: You are building or cleaning a string one character at a time and want to avoid copying it over and over.

Not this when

  • No: You need the longest or shortest stretch of text that obeys a rule. The string is only the array there: use a sliding window.
  • No: You must look up many words by prefix, like autocomplete. A trie shares prefixes, which a plain string can't.
  • No: You are counting whole words or other keys, not letters. A hash map is the tool, and a string is only its key.

Which pattern fits?

  1. Which pattern? 1 of 5

    Decide whether two words, like "listen" and "silent", use exactly the same letters the same number of times.

  2. Which pattern? 2 of 5

    Given a string, find the length of the longest substring that has no repeating characters.

  3. Which pattern? 3 of 5

    A dictionary holds 100,000 words. Quickly tell whether any word starts with the prefix "pre".

  4. Which pattern? 4 of 5

    Count how many times each word appears in a long log file and report the most frequent one.

  5. Which pattern? 5 of 5

    Turn a spreadsheet column title like "AB" into its number, where A is 1, B is 2, ... Z is 26 and AA is 27.

The code

First the idea in plain steps. Then the same idea as real code, line for line.

Pseudocode
  1. 1left = 0, right = last index of s
  2. while left < right:
  3. 2if s[left] is not a letter or digit: left += 1
  4. 2else if s[right] is not a letter or digit: right -= 1
  5. 3else if s[left] and s[right] differ, ignoring case:
  6. 5return false
  7. 4else: left += 1 and right -= 1
  8. 5return true

The faint numbers are the rules in the Rule Rail under the stage. Same numbers, same order.

Getting the replay ready…

def is_palindrome(s):
    left = 0
    right = 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
Time · O(n)Space · O(1) extra, just two indexes
  • Every loop step moves at least one pointer, and pointers only move toward each other, so there are at most n steps in total. Only left and right are stored.
  • The "filter, lower-case, reverse, compare" version is also correct and simpler to read, but it builds new strings, so it uses O(n) extra space. The pointer version makes no copy at all.
  • Letters are numbers. 'a' is 97, so ch - 'a' maps a to z onto 0 to 25. That is why lowercase letters can be counted in a plain 26-slot array. The anagram tracer draws a 5-bucket hash table (bucket = code % 5) so you can watch collisions, but a 26-slot array gives the same counts.
  • Building a string in a loop. Java: `s += ch` makes a new String and copies everything built so far each time, so n appends cost O(n²). Use a StringBuilder and append, which is O(n) overall. Python: collect the pieces in a list and call ''.join(pieces).
  • Python's `s += ch` is not always quadratic. CPython can sometimes grow the string in place when nothing else refers to it, so it may look fast. That is an implementation detail, not a promise, so ''.join is the safe habit. C++ std::string is mutable and `+=` appends in place, about O(1) per character on average, though inserting or erasing at the front still shifts everything.
  • Slicing copies. Python s[a:b], Java s.substring(a, b) and C++ s.substr(a, b) each copy their characters, so slicing inside a loop adds up. Pass indexes instead, as the pointer solution does.
  • In C++ cast to unsigned char before calling std::isalnum or std::tolower on a char, because a negative char value is undefined behaviour. Python and Java's checks also accept non-ASCII letters, which this lesson doesn't cover.

Worked examples

Real interview problems, solved with the same recipe.

Open on LeetCode (opens in a new tab)

A phrase is a palindrome if, after making every letter lower case and removing everything that is not a letter or digit, it reads the same forwards and backwards. Given a string s, return true if it is a palindrome.

Input

s = "Race car!"

Output

true

Approach

  1. The easy way builds a cleaned, lower-case copy, reverses it and compares. It works, but it makes new strings. Two pointers need no copy.
  2. Put left on the first character and right on the last. If a pointer sits on something that isn't a letter or digit, move that pointer inward.
  3. When both pointers are on real characters, compare them ignoring case. A difference means false. A match moves both pointers inward.
  4. If the pointers meet or cross with no mismatch, return true. Here the '!' and the space are skipped, and R = r, a = a, c = c.
def is_palindrome(s):
    left = 0
    right = 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
Time · O(n)Space · O(1)

Knowledge check

Test yourself first. Try to answer these in your own words, then take the quiz below to check.

  1. In Java you build a 10,000-character result with `s += ch` inside a loop. What happens, and what should you use instead?
  2. A friend says a Python `s += ch` loop ran fast on their machine. Why is ''.join(pieces) still the safe habit?
  3. What does 'z' - 'a' give in Java or C++, and why does that make a 26-slot count array possible?
  4. While spending the letters of t against the counts of s (the two words have equal length), when does the anagram check return false?
  5. How does the two-pointer palindrome check compare with "filter, lower-case, reverse, compare"?

Question 1 of 5

In Java you build a 10,000-character result with `s += ch` inside a loop. What happens, and what should you use instead?

Assignment

Pick one, try it cold for ten minutes, then come back for the hint.

0 of 8 solved

  1. Solve Reverse String (opens in a new tab) (LeetCode, easy)

    Hint: The input is an array of characters you may change in place, so ask which two positions should swap, and where the pointers stop.

  2. Solve Valid Palindrome II (opens in a new tab) (LeetCode, easy)

    Hint: Run the palindrome pointers as usual. At the first mismatch you may drop one character, so check both ways of dropping it.

  3. Solve First Unique Character in a String (opens in a new tab) (LeetCode, easy)

    Hint: Count every letter first, then walk the string again and stop at the first letter whose count is exactly 1.

  4. Solve Longest Common Prefix (opens in a new tab) (LeetCode, easy)

    Hint: A common prefix can't be longer than the shortest word. Compare column by column and stop at the first column where any word disagrees.

  5. Solve Remove All Adjacent Duplicates In String (opens in a new tab) (LeetCode, easy)

    Hint: Build the answer one character at a time in a StringBuilder or list, and look at its last character to decide whether the new one cancels it.

  6. Solve Longest Palindromic Substring (opens in a new tab) (LeetCode, medium)

    Hint: Every palindrome has a centre. Try each centre, widen outward while the ends match, and remember both odd and even lengths.

  7. Solve Find All Anagrams in a String (opens in a new tab) (LeetCode, medium)

    Hint: Slide a window as long as the pattern over the text, keeping letter counts that you update as one letter enters and one leaves.

  8. Solve Minimum Window Substring (opens in a new tab) (LeetCode, hard)

    Hint: Count what the window still needs. Grow it until nothing is missing, then shrink from the left for as long as it stays valid.

Additional resources