Why Strings Are a Data Structure Not Just Text in DSA Rust - Why This Pattern

Mental Model

A string is more than just letters; it is a collection of characters stored in order with extra information to help us use it efficiently.

Analogy: Think of a string like a bead necklace where each bead is a letter. The necklace has a clasp that tells you how many beads there are and how to find each one quickly.

String: [H] -> [e] -> [l] -> [l] -> [o] -> null
Length: 5
Index: 0    1    2    3    4

Dry Run Walkthrough

Input: string: "Hello" stored as characters with length 5

Goal: Show how string stores characters and length to allow quick access and operations

Step 1: Store characters 'H', 'e', 'l', 'l', 'o' in order

[H] -> [e] -> [l] -> [l] -> [o] -> null
Length: 5

Why: We need to keep characters in order to read the string correctly

Step 2: Store length 5 separately

[H] -> [e] -> [l] -> [l] -> [o] -> null
Length: 5

Why: Knowing length helps quickly find string size without counting each character

Step 3: Access character at index 1 (second character)

[H] -> [e] -> [l] -> [l] -> [o] -> null
Accessed: 'e'

Why: Indexing lets us get any character fast without scanning whole string

Result:

[H] -> [e] -> [l] -> [l] -> [o] -> null
Length: 5
Access at index 1: 'e'

Annotated Code

DSA Rust

struct MyString {
    chars: Vec<char>,
    length: usize,
}

impl MyString {
    fn new(s: &str) -> Self {
        let chars: Vec<char> = s.chars().collect();
        let length = chars.len();
        MyString { chars, length }
    }

    fn char_at(&self, index: usize) -> Option<char> {
        if index < self.length {
            Some(self.chars[index])
        } else {
            None
        }
    }

    fn print(&self) {
        for c in &self.chars {
            print!("{}", c);
        }
        println!("\nLength: {}", self.length);
    }
}

fn main() {
    let s = MyString::new("Hello");
    s.print();
    match s.char_at(1) {
        Some(c) => println!("Character at index 1: {}", c),
        None => println!("Index out of bounds"),
    }
}

let chars: Vec<char> = s.chars().collect();

convert input text to a list of characters to store in order

let length = chars.len();

store the length of the string for quick size access

if index < self.length {

check if requested index is valid to avoid errors

Some(self.chars[index])

return character at given index for fast access

Output

Hello

Length: 5

Character at index 1: e

Complexity Analysis

Time: O(1) for accessing a character because we use indexing; O(n) to create string because we copy all characters once

Space: O(n) because we store all characters plus length

vs Alternative: Compared to just raw text, storing length and characters separately allows faster operations like length queries and indexing without scanning

Edge Cases

empty string ""

length is 0 and chars list is empty; accessing any index returns None

DSA Rust

if index < self.length {

index out of bounds (e.g., index 10 in "Hello")

char_at returns None safely without crashing

DSA Rust

if index < self.length {

When to Use This Pattern

When a problem involves storing text with fast access to characters or length, think of strings as data structures with indexing and length fields to optimize operations.

Common Mistakes

Mistake: Treating strings as just raw text without length or indexing, causing slow operations
Fix: Store characters in a list and keep track of length to enable fast access

Summary

Strings store characters in order plus length to allow quick access and size queries.

Use this structure when you need to read, index, or measure text efficiently.

The key insight is that strings are organized data, not just plain text.

Practice

1. Why are strings considered a data structure and not just plain text in Rust?

easy

A. Because strings cannot be changed once created

B. Because strings are only used for printing text

C. Because strings store characters in a sequence with indexing and length properties

D. Because strings are always fixed size arrays

Solution

1. Step 1: Understand what a data structure is

   A data structure organizes data to allow operations like indexing, length checking, and iteration.

2. Step 2: Analyze string properties in Rust

   Rust strings store characters in order, support length queries, and allow access to parts, so they behave like a data structure.

3. Final Answer:

   Because strings store characters in a sequence with indexing and length properties -> Option C

4. Quick Check:

   Strings = Data structure [OK]

Hint: Strings hold ordered characters with length and indexing [OK]

Common Mistakes:

• Thinking strings are just plain text without structure
• Assuming strings are immutable fixed arrays
• Confusing strings with single characters

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

easy

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

B. let s = 'hello';

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

D. let s = String::from("hello");

Solution

1. Step 1: Identify mutable string creation syntax

   In Rust, to create a mutable String, you declare it with mut and initialize with String::new() or String::from().

2. Step 2: Verify the correct syntax

   The correct way is let mut s = String::new();, which creates an empty mutable String. Without mut the String is immutable. Single quotes denote characters, not strings, and String::from() requires a string slice like "hello".

3. Final Answer:

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

4. Quick Check:

   Mutable String = let mut s = String::new(); [OK]

Hint: Use 'mut' keyword to make String mutable [OK]

Common Mistakes:

• Forgetting 'mut' keyword for mutability
• Using single quotes for strings instead of double quotes
• Confusing &str with String type

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

let mut s = String::from("hello");
s.push_str(", world!");
println!("{}", s);

medium

A. "hello"

B. "hello, world!"

C. Compilation error

D. "hello world"

Solution

1. Step 1: Understand push_str method

   The push_str method appends a string slice to the existing String.

2. Step 2: Trace the code execution

   Initially, s = "hello". After s.push_str(", world!"), s becomes "hello, world!". The print statement outputs this full string.

3. Final Answer:

   "hello, world!" -> Option B

4. Quick Check:

   push_str appends text = "hello, world!" [OK]

Hint: push_str adds text to String, so output includes appended text [OK]

Common Mistakes:

• Expecting original string without appended text
• Confusing push_str with push (which adds single char)
• Thinking code causes compile error

4. Identify the error in this Rust code snippet:

let s = String::from("hello");
s.push('!');

medium

A. Cannot push a character to an immutable String

B. push method does not exist for String

C. Missing semicolon after push

D. String::from cannot create a String

Solution

1. Step 1: Check mutability of String

   The variable s is declared without mut, so it is immutable.

2. Step 2: Understand push method requirements

   The push method modifies the String by adding a character, which requires the String to be mutable.

3. Final Answer:

   Cannot push a character to an immutable String -> Option A

4. Quick Check:

   push needs mutable String = error if not mutable [OK]

Hint: Make String mutable with 'mut' before push [OK]

Common Mistakes:

• Ignoring mut keyword requirement
• Thinking push is invalid method
• Assuming missing semicolon causes error

5. Given a String in Rust, how can you efficiently count the number of characters (not bytes) it contains?

hard

A. Use s.capacity() to find character count

B. Use s.len() to get the character count

C. Use s.bytes().count() to count characters

D. Convert to chars iterator and count elements with s.chars().count()

Solution

1. Step 1: Understand difference between bytes and characters

   Rust strings store UTF-8 bytes; len() returns byte count, not character count.

2. Step 2: Use chars iterator to count characters

   The chars() method returns an iterator over Unicode scalar values (characters). Counting these gives the correct character count.

3. Final Answer:

   Convert to chars iterator and count elements with s.chars().count() -> Option D

4. Quick Check:

   chars().count() = character count [OK]

Hint: Use s.chars().count() for accurate character count [OK]

Common Mistakes:

• Using s.len() which counts bytes, not characters
• Using bytes().count() which counts bytes
• Confusing capacity() with length