How Strings Work Differently Across Languages in DSA Rust - Step-by-Step

Mental Model

Strings are sequences of characters, but how they are stored and changed depends on the language's rules and memory model.

Analogy: Think of strings like different types of notebooks: some let you erase and rewrite easily (mutable), others are like printed books you can't change (immutable), and some keep track of pages separately (like bytes vs characters).

Rust String (mutable, heap):
[String] -> [chars in heap memory]

Rust &str (immutable slice):
&str -> [fixed chars in memory]

Python str (immutable):
str -> [fixed chars in memory]

C string (null-terminated):
char[] -> [chars] -> '\0'

Dry Run Walkthrough

Input: Create a Rust String from "hello", append " world", then print it.

Goal: Show how Rust's String can grow because it owns heap memory, unlike fixed slices.

Step 1: Create a String with "hello" stored in heap memory

String -> [h e l l o] in heap

Why: We need a mutable string that owns its data to allow changes

Step 2: Append " world" to the String

String -> [h e l l o   w o r l d] in heap

Why: String can grow because it manages heap memory dynamically

Step 3: Print the String

Output: "hello world"

Why: Shows the final combined string after mutation

Result:

String -> [h e l l o   w o r l d] in heap
Output: "hello world"

Annotated Code

DSA Rust

fn main() {
    // Step 1: Create a mutable String owning heap data
    let mut s = String::from("hello");
    // Step 2: Append " world" to the String
    s.push_str(" world");
    // Step 3: Print the final String
    println!("{}", s);
}

let mut s = String::from("hello");

Create a mutable String that owns its data on the heap

s.push_str(" world");

Append more characters by growing the heap allocation

println!("{}", s);

Print the current state of the String

Output

hello world

Complexity Analysis

Time: O(n) because appending may require copying existing characters to a larger heap space

Space: O(n) because the String stores characters on the heap and grows as needed

vs Alternative: Compared to &str slices which are fixed and immutable, String allows dynamic changes but uses more memory and time to manage heap

Edge Cases

Empty String creation

Creates an empty heap allocation ready to grow

DSA Rust

let mut s = String::new();

Appending to a very large String

Heap reallocates to accommodate new data, may be slower

DSA Rust

s.push_str(" world");

Using &str slice instead of String

Cannot append because &str is immutable and fixed size

DSA Rust

let s = "hello"; // &str cannot push_str

When to Use This Pattern

When you see string manipulation in Rust or other languages, check if the string is mutable and owns its data (like Rust's String) or is an immutable slice (like &str), because this affects how you can change it.

Common Mistakes

Mistake: Trying to append to an immutable string slice (&str)
Fix: Use a mutable String type instead of &str to allow changes

Summary

Strings store characters but differ in mutability and memory ownership across languages.

Use mutable owned strings when you need to change or grow text dynamically.

The key insight is that some strings are fixed and read-only, while others manage memory to allow changes.

Practice

1. In Rust, which of the following best describes how String differs from string types in some other languages like Python or JavaScript?

easy

A. String in Rust is immutable and fixed-length like Python strings.

B. String in Rust is a growable, heap-allocated UTF-8 encoded string.

C. String in Rust stores characters as UTF-16 code units internally.

D. String in Rust is a simple alias for a byte array without encoding.

Solution

1. Step 1: Understand Rust's String type

   Rust's String is designed to be growable and stored on the heap, unlike fixed-length strings in some languages.

2. Step 2: Compare with other languages

   Languages like Python have immutable strings, and JavaScript strings are UTF-16 encoded internally, but Rust uses UTF-8 encoding for String.

3. Final Answer:

   String in Rust is a growable, heap-allocated UTF-8 encoded string. -> Option B

4. Quick Check:

   Rust String = growable UTF-8 heap string [OK]

Hint: Remember Rust strings are UTF-8 and growable, unlike fixed immutable strings [OK]

Common Mistakes:

• Thinking Rust strings are immutable like Python strings
• Assuming Rust strings use UTF-16 encoding
• Confusing String with byte arrays without encoding

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

easy

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

B. let s = "hello";

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

D. let s = "hello".to_string();

Solution

1. Step 1: Identify mutable string creation syntax

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

2. Step 2: Check each option

   let s = "hello"; creates an immutable string slice (&str), not a String. let mut s = String::from("hello"); correctly creates a mutable String. let s = String::new("hello"); is invalid syntax. let s = "hello".to_string(); creates a String but lacks mut, making the binding immutable.

3. Final Answer:

   let mut s = String::from("hello"); -> Option A

4. Quick Check:

   Mutable String = let mut s = String::from(...) [OK]

Hint: Use let mut s = String::from(...) for mutable strings [OK]

Common Mistakes:

• Using string literals without mut for mutability
• Trying to use String::new("hello") which is invalid
• Confusing string slices with String type

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

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

medium

A. Runtime panic due to invalid UTF-8 slicing

B. he

C. h

D. hello

Solution

1. Step 1: Understand Rust string slicing rules

   Rust strings are UTF-8 encoded, so slicing must be on valid UTF-8 boundaries. Index 0..1 slices the first byte only.

2. Step 2: Check if slicing 0..1 is valid UTF-8

   For "hello", ASCII characters are 1 byte each, so 0..1 is valid and equals "h".

3. Step 3: Confirm output

   println!("{}", h) where h = &s[0..1] = "h" outputs h.

4. Final Answer:

   h -> Option C

5. Quick Check:

   Slice 0..1 of "hello" = "h" [OK]

Hint: Remember ASCII chars are 1 byte, so 0..1 slice is valid [OK]

Common Mistakes:

• Assuming slicing 0..1 causes panic always
• Confusing byte index with character index
• Expecting multiple characters from 0..1 slice

4. Identify the error in this Rust code snippet:

let s = String::from("Здравствуйте");
let slice = &s[0..1];
println!("{}", slice);

medium

A. No error, prints first character

B. Prints garbage characters

C. Compile-time error: invalid slice syntax

D. Runtime panic: slicing not on UTF-8 boundary

Solution

1. Step 1: Analyze the string content and slicing

   The string "Здравствуйте" contains Cyrillic characters, each encoded in multiple bytes in UTF-8.

2. Step 2: Check slicing 0..1 validity

   Slicing 0..1 takes only the first byte, which is not a valid UTF-8 character boundary for Cyrillic letters, causing a runtime panic.

3. Final Answer:

   Runtime panic: slicing not on UTF-8 boundary -> Option D

4. Quick Check:

   UTF-8 multi-byte chars require valid slice boundaries [OK]

Hint: Multi-byte UTF-8 chars cannot be sliced by single bytes [OK]

Common Mistakes:

• Assuming slicing always works like ASCII
• Ignoring UTF-8 multi-byte character boundaries
• Expecting compile-time error instead of runtime panic

5. Given a Rust String containing Unicode text, which approach correctly iterates over each Unicode character safely?

hard

A. Using for c in s.chars() to iterate over Unicode scalar values.

B. Using for i in 0..s.len() and slicing &s[i..i+1] for each byte.

C. Using for c in s.bytes() to get each character.

D. Using for c in s.split(' ') to get characters.

Solution

1. Step 1: Understand Rust string iteration methods

   s.chars() iterates over Unicode scalar values (characters) safely, respecting UTF-8 boundaries.

2. Step 2: Evaluate other options

   Using for i in 0..s.len() and slicing &s[i..i+1] slices bytes which can cause invalid UTF-8. for c in s.bytes() iterates bytes, not characters. for c in s.split(' ') splits by spaces, not characters.

3. Final Answer:

   Using for c in s.chars() to iterate over Unicode scalar values. -> Option A

4. Quick Check:

   Use s.chars() for safe Unicode iteration [OK]

Hint: Use s.chars() to safely iterate Unicode characters [OK]

Common Mistakes:

• Iterating bytes instead of characters
• Slicing string by byte indices unsafely
• Using split which divides by delimiter, not characters