String Basics and Memory Representation in DSA Rust

Mental Model

A string is a sequence of characters stored in memory one after another, with a pointer to the start and a length to know how many characters it holds.

Analogy: Think of a string like a train where each carriage holds one letter, and the engine points to the first carriage while a counter tells how many carriages are connected.

String: [H] -> [e] -> [l] -> [l] -> [o]
Pointer ↑
Length: 5

Dry Run Walkthrough

Input: Create string "Hello" and show its memory layout

Goal: Understand how characters are stored in memory and how the string knows its length

Step 1: Allocate memory for 5 characters

[ ] [ ] [ ] [ ] [ ]
Pointer ↑
Length: 0

Why: We need space to store each character of the string

Step 2: Store 'H' in first slot

[H] [ ] [ ] [ ] [ ]
Pointer ↑
Length: 1

Why: First character is placed at the start

Step 3: Store 'e' in second slot

[H] -> [e] [ ] [ ] [ ]
Pointer ↑
Length: 2

Why: Second character follows the first

Step 4: Store 'l' in third slot

[H] -> [e] -> [l] [ ] [ ]
Pointer ↑
Length: 3

Why: Third character continues the sequence

Step 5: Store 'l' in fourth slot

[H] -> [e] -> [l] -> [l] [ ]
Pointer ↑
Length: 4

Why: Fourth character added

Step 6: Store 'o' in fifth slot

[H] -> [e] -> [l] -> [l] -> [o]
Pointer ↑
Length: 5

Why: Fifth character completes the string

Result:

Memory layout: [H] -> [e] -> [l] -> [l] -> [o]
Pointer points to first character
Length is 5

Annotated Code

DSA Rust

struct MyString {
    ptr: *const u8, // pointer to first character
    length: usize,  // number of characters
}

impl MyString {
    fn new(s: &str) -> Self {
        let bytes = s.as_bytes();
        let ptr = bytes.as_ptr();
        let length = bytes.len();
        MyString { ptr, length }
    }

    fn print(&self) {
        unsafe {
            for i in 0..self.length {
                let c = *self.ptr.add(i) as char;
                print!("{}", c);
            }
        }
        println!();
    }
}

fn main() {
    let s = MyString::new("Hello");
    s.print();
}

let bytes = s.as_bytes();

convert string slice to byte array for memory access

let ptr = bytes.as_ptr();

store pointer to first byte of string

let length = bytes.len();

store length of string for iteration

for i in 0..self.length {

iterate over each character index

let c = *self.ptr.add(i) as char;

access character at current index via pointer arithmetic

print!("{}", c);

print character without newline

Output

Hello

Complexity Analysis

Time: O(n) because printing requires visiting each character once

Space: O(n) because the string stores all characters in contiguous memory

vs Alternative: Compared to linked list of characters, this uses less memory and allows fast access by index

Edge Cases

Empty string ""

Pointer is valid but length is zero, so no characters are accessed

DSA Rust

for i in 0..self.length {

String with one character "A"

Pointer points to single character, length is one, print outputs one character

DSA Rust

for i in 0..self.length {

When to Use This Pattern

When you see a problem about storing or accessing text efficiently, think of strings as contiguous memory with a pointer and length to quickly find characters.

Common Mistakes

Mistake: Trying to access characters without checking length, causing out-of-bounds errors
Fix: Always use the stored length to limit access within valid memory

Summary

A string stores characters in a row in memory with a pointer to the start and a length to know how many characters it holds.

Use this when you need to store and access text efficiently by index.

The key insight is that a string is just a pointer plus a length, not a linked list of characters.

Practice

1. What does the String type in Rust represent?

easy

A. A growable, heap-allocated string

B. A fixed-size array of characters

C. A pointer to a string literal

D. An immutable string slice

Solution

1. Step 1: Understand Rust string types

   Rust has two main string types: String and string slices (&str). String is growable and stored on the heap.

2. Step 2: Compare options with definitions

   A growable, heap-allocated string correctly describes String as growable and heap-allocated. Others describe slices or fixed arrays.

3. Final Answer:

   A growable, heap-allocated string -> Option A

4. Quick Check:

   String = growable heap string [OK]

Hint: Remember: String is growable and heap-allocated [OK]

Common Mistakes:

• Confusing String with &str (string slice)
• Thinking String is fixed size
• Assuming String is immutable

2. Which of the following is the correct way to create a new empty String in Rust?

easy

A. let s = String::new();

B. let s = String();

C. let s = new String();

D. let s = String[];

Solution

1. Step 1: Recall Rust String creation syntax

   In Rust, String::new() creates a new empty String.

2. Step 2: Check each option syntax

   let s = String::new(); uses correct Rust syntax. The other options use invalid Rust syntax for creating a String.

3. Final Answer:

   let s = String::new(); -> Option A

4. Quick Check:

   String::new() creates empty String [OK]

Hint: Use String::new() to create empty String [OK]

Common Mistakes:

• Using parentheses like a function call without ::new()
• Trying to use new keyword like other languages
• Using array brackets for String

3. What will be the output of this Rust code?

let s = String::from("hello");
let slice = &s[0..2];
println!("{}", slice);

medium

A. Runtime error

B. hel

C. hello

D. he

Solution

1. Step 1: Understand string slicing in Rust

   The slice &s[0..2] takes characters from index 0 up to but not including 2.

2. Step 2: Extract substring from "hello"

   Characters at index 0 and 1 are 'h' and 'e', so the slice is "he".

3. Final Answer:

   he -> Option D

4. Quick Check:

   Slice 0..2 of "hello" = "he" [OK]

Hint: Slice 0..n means characters from 0 up to n-1 [OK]

Common Mistakes:

• Assuming slice includes index 2
• Expecting full string output
• Thinking slicing causes runtime error

4. Identify the error in this Rust code snippet:

let s = String::from("hello");
let slice = &s[0..4];
println!("{}", slice);
let ch = &s[4];

medium

A. Slice range 0..4 is invalid

B. Cannot index String with single usize

C. Missing semicolon after println!

D. String::from is not valid

Solution

1. Step 1: Check indexing rules for String

   Rust does not allow indexing a String with a single usize like s[4] because strings are UTF-8 encoded and indexing by byte is unsafe.

2. Step 2: Verify other parts

   Slice &s[0..4] is valid. Semicolons and String::from usage are correct.

3. Final Answer:

   Cannot index String with single usize -> Option B

4. Quick Check:

   Single index on String causes error [OK]

Hint: Use slices, not single index, to access String parts [OK]

Common Mistakes:

• Trying to access String by single index
• Confusing slice range validity
• Ignoring Rust UTF-8 string rules

5. Given a UTF-8 encoded Rust String containing emoji and letters, which method safely returns the number of characters (not bytes)?

hard

A. s.len()

B. s.as_bytes().len()

C. s.chars().count()

D. s.bytes().count()

Solution

1. Step 1: Understand difference between bytes and characters

   UTF-8 strings store characters as 1 or more bytes. len() returns byte count, not character count.

2. Step 2: Identify method counting characters

   s.chars().count() iterates over Unicode scalar values (characters) and counts them correctly.

3. Final Answer:

   s.chars().count() -> Option C

4. Quick Check:

   chars().count() counts characters, not bytes [OK]

Hint: Use chars().count() for character count, not len() [OK]

Common Mistakes:

• Using len() which counts bytes, not characters
• Confusing bytes() with chars()
• Assuming as_bytes().len() counts characters