Strings in Rust

A string is text. Inside the computer, text is stored as a row of bytes, and a rule called an encoding says which bytes mean which letters. Rust uses UTF-8, the encoding most of the world's software uses. In UTF-8, each English letter takes one byte, but many other characters take more. The letter é takes two bytes, and a letter from Hindi such as अ takes three.

That one fact explains most of what is unusual about strings in Rust. Reach for a string whenever your data is text: names, words, lines of input, patterns to search for.

Rust has two main string types:

• String owns its text. It lives in memory it controls, it can grow, and it is cleaned up automatically when it goes out of use.
• &str (say "string slice") is a borrowed view of text that lives somewhere else. It can't grow, and it doesn't own anything.

A piece of text written directly in the code, like "hello", is a &str. A rule of thumb that works well: take &str as a parameter, return String when you build new text.

The word héllo has five characters but six bytes. The top row of the picture is what a reader sees. The bottom row is what is stored, with each byte numbered from zero and shown in hexadecimal (base 16, which is how bytes are usually written).

This is why word.len() says 6: len counts bytes. To count characters you have to walk the text and count as you go, which is what word.chars().count() does.

It also explains why Rust won't let you write word[1]. What should that mean: byte 1, or the second character? Here, byte 1 is half of é, which is not a character at all. Whichever answer Rust picked would either hide a slow walk or hand you a broken piece of a character, so it picks neither and gives a compile error. You have to say what you mean: word.chars().nth(1) for the second character, or a slice like &word[0..1] for a range of bytes.

Slicing by bytes is allowed, but the cut points must fall on the edge between two characters. The dashed line in the picture marks a cut at byte 2, which lands in the middle of é. A slice that ends there panics.

First, a function that returns part of its input.

/// The text up to the first space, or all of it if there is no space.
/// The result borrows from `text`: it is a window onto the same bytes.
pub fn first_word(text: &str) -> &str {
    match text.find(' ') {
        Some(end) => &text[..end],
        None => text,
    }
}

text.find(' ') searches for the first space and gives back an Option<usize>: Some(position) if it found one, None if not. A space is a single byte, so its position is always a clean cut point, and &text[..end] is safe.

The result is a &str that points into text. Nothing is copied. Because it points into the input, Rust treats it as borrowed from the input, and it can't outlive it. Rust works this out for you in a simple case like this one, which is called lifetime elision: one input reference and one output reference means the output is tied to the input.

Second, a function that builds new text.

/// Builds a brand new `String`, so the caller owns the result.
pub fn shout(text: &str) -> String {
    let mut out = String::new();
    for c in text.chars() {
        out.push(c.to_ascii_uppercase());
    }
    out.push('!');
    out
}

String::new() makes an empty String. It has to be mut (changeable) because we push onto it. out.push(c) adds one character and push_str adds a whole piece of text. The function returns out, so ownership of the new String moves to the caller, who can keep it for as long as they like.

Third, one that counts.

pub fn count_vowels(text: &str) -> usize {
    text.chars()
        .filter(|c| matches!(c.to_ascii_lowercase(), 'a' | 'e' | 'i' | 'o' | 'u'))
        .count()
}

text.chars() walks the characters one at a time. .filter(...) keeps the ones where the closure says true. A closure is a small unnamed function written between pipes: |c| ... takes c and returns a value. matches! checks a value against several patterns. .count() then counts what is left.

Everything above was to show how it works. In real code, use what the standard library has. Here are the two types side by side.

let literal: &str = "hello"; // borrowed text, baked into the program
let mut owned: String = literal.to_string(); // owned, and able to grow
owned.push_str(", world");

let view: &str = &owned; // a borrowed view of `owned`
assert_eq!(view, "hello, world");
assert_eq!(literal, "hello"); // `literal` was never touched

to_string() makes a new owned String from borrowed text, by copying it. push_str can then grow it. Notice that literal is still fine afterwards, since the copy was independent.

And here is the length and indexing story from earlier, in code.

let word = "héllo";
assert_eq!(word.len(), 6); // bytes: the é takes two
assert_eq!(word.chars().count(), 5); // characters

// let c = word[1]; // error: `str` cannot be indexed by an integer
assert_eq!(word.chars().nth(1), Some('é'));
assert_eq!(&word[0..1], "h"); // slicing by byte range is allowed...
assert!(!word.is_char_boundary(2)); // ...but not through the middle of é

When you do need to know where each character is, char_indices pairs every character with the byte position where it starts:

let word = "héllo";
let positions: Vec<(usize, char)> = word.char_indices().collect();
assert_eq!(positions[1], (1, 'é'));
assert_eq!(positions[2], (3, 'l')); // the next character starts at byte 3

Notice the l after é starts at byte 3, not 2, because é took bytes 1 and 2.

A few more methods you will use all the time, all on &str:

• len() and is_empty() give the size in bytes and whether it is zero.
• chars() and bytes() walk the text by character or by byte.
• contains("ab"), starts_with("ab") and find("ab") search.
• split_whitespace() splits into words, and trim() removes spaces at both ends.
• to_lowercase() and to_uppercase() return a new String.
• parse::<i32>() turns text such as "42" into a number, and tells you if it can't.

The row to remember is chars().nth(i). On an array, reading item i is instant. On text, reading character i costs i steps, because characters have different widths and the only way to find the ith is to count. If an algorithm needs to jump around by position, it is common to collect the characters into a Vec<char> first, which then costs O(n) space but allows O(1) reads. Problem 1 does exactly that.

Problems 2 and 3 use a trick worth learning: when the text is only the letters a to z, an array of 26 counters is a perfect and cheap tally. Its size never changes with the input, so it counts as O(1) space.

pub fn is_palindrome(text: &str) -> bool {
    todo!("ignore case and anything that is not a letter or digit")
}

pub fn is_palindrome(text: &str) -> bool {
    let chars: Vec<char> = text
        .chars()
        .filter(|c| c.is_alphanumeric())
        .flat_map(|c| c.to_lowercase())
        .collect();

    if chars.is_empty() {
        return true;
    }
    let mut left = 0;
    let mut right = chars.len() - 1;
    while left < right {
        if chars[left] != chars[right] {
            return false;
        }
        left += 1;
        right -= 1;
    }
    true
}

pub fn is_anagram(a: &str, b: &str) -> bool {
    todo!("same letters, same counts; both inputs are lowercase a-z")
}

pub fn is_anagram(a: &str, b: &str) -> bool {
    if a.len() != b.len() {
        return false;
    }
    let mut counts = [0i32; 26];
    for byte in a.bytes() {
        counts[(byte - b'a') as usize] += 1;
    }
    for byte in b.bytes() {
        counts[(byte - b'a') as usize] -= 1;
    }
    counts.iter().all(|&c| c == 0)
}

pub fn first_unique_char(text: &str) -> Option<usize> {
    todo!("byte index of the first letter that appears once; lowercase a-z")
}

pub fn first_unique_char(text: &str) -> Option<usize> {
    let mut counts = [0usize; 26];
    for byte in text.bytes() {
        counts[(byte - b'a') as usize] += 1;
    }
    text.bytes()
        .position(|byte| counts[(byte - b'a') as usize] == 1)
}

String problems turn up often in coding tests and interviews, partly because they look easy and have a lot of edge cases. A few habits help.

• Ask about the alphabet. Is the text only lowercase a to z? Is it ASCII? Could it hold any Unicode? The answer decides whether a 26-slot array is enough, and whether you can treat one byte as one character.
• Ask what to ignore. Should case matter? Should spaces and punctuation count? Palindrome questions especially vary here.
• Count with an array when you can. A fixed array of counters is simple and quick. For a bigger alphabet you would use a hash map, which comes in lesson 6.
• In Rust, say whether you are working with bytes or characters. Explaining that you used bytes() because the input is ASCII, or chars() because it might not be, shows you understand why Rust won't let you index a string by number.
• Say the cost. "Two passes over the text, so O(n) time, and a fixed array, so O(1) space" is a complete and honest answer.

Made by VeraStack Labs