String Traversal and Character Access in DSA Rust

Mental Model

A string is a sequence of characters that we can look at one by one from start to end.

Analogy: Imagine reading a sentence letter by letter from left to right to understand each word.

"H" -> "e" -> "l" -> "l" -> "o" -> null
 ↑
 current position at first character

Dry Run Walkthrough

Input: string: "Rust"

Goal: Print each character in the string one by one

Step 1: Start at the first character

"R" -> "u" -> "s" -> "t" -> null
 ↑

Why: We begin reading from the first character

Step 2: Print the current character 'R' and move to next

"R" -> "u" -> "s" -> "t" -> null
     ↑

Why: We read and output the first character, then move forward

Step 3: Print the current character 'u' and move to next

"R" -> "u" -> "s" -> "t" -> null
          ↑

Why: Continue reading characters in order

Step 4: Print the current character 's' and move to next

"R" -> "u" -> "s" -> "t" -> null
               ↑

Why: Keep traversing until the end

Step 5: Print the current character 't' and move to end

"R" -> "u" -> "s" -> "t" -> null
                    ↑

Why: Last character to print before finishing

Result:

Printed characters: R\nu\ns\nt\n

Annotated Code

DSA Rust

fn main() {
    let s = String::from("Rust");
    for c in s.chars() {
        println!("{}", c); // print each character on a new line
    }
}

for c in s.chars() {

iterate over each character in the string in order

println!("{}", c);

print the current character and move to the next

Output

R

u

s

t

Complexity Analysis

Time: O(n) because we visit each character once

Space: O(1) because we only store one character at a time during traversal

vs Alternative: Compared to indexing by byte which can be unsafe for multi-byte chars, using chars() safely handles Unicode characters

Edge Cases

empty string

The loop does not run and nothing is printed

DSA Rust

for c in s.chars() {

string with multi-byte Unicode characters like "😊"

Each Unicode character is correctly accessed and printed as one unit

DSA Rust

for c in s.chars() {

When to Use This Pattern

When you need to process or examine each character in a string safely, use string traversal with character access to handle all characters correctly.

Common Mistakes

Mistake: Trying to index a string by position directly which can cause errors with multi-byte characters
Fix: Use the chars() iterator to access characters safely instead of indexing

Summary

It goes through a string one character at a time to read or process each character.

Use it when you want to look at or print every character in a string safely.

The key is to use the chars() method to handle all characters correctly, including Unicode.

Practice

1. What does the following Rust code print?
let s = "hello";
for c in s.chars() {
print!("{}-", c);
}

easy

A. h-e-l-l-o-

B. hello

C. h e l l o

D. h,e,l,l,o,

Solution

1. Step 1: Understand the chars() method

   The chars() method returns an iterator over each character in the string s.

2. Step 2: Trace the for loop printing

   Each character is printed followed by a dash, so output is h-e-l-l-o-.

3. Final Answer:

   h-e-l-l-o- -> Option A

4. Quick Check:

   chars() + print with dash = h-e-l-l-o- [OK]

Hint: chars() iterates characters; print each with dash [OK]

Common Mistakes:

• Thinking chars() returns words
• Ignoring the dash printed after each char
• Confusing chars() with bytes()

2. Which of the following is the correct way to access the third character of a Rust string s safely?

easy

A. let c = s.bytes().nth(2).unwrap();

B. let c = s[2];

C. let c = s.get(2).unwrap();

D. let c = s.chars().nth(2).unwrap();

Solution

1. Step 1: Understand string indexing in Rust

   Rust strings cannot be indexed directly by integer due to UTF-8 encoding, so s[2] is invalid.

2. Step 2: Use chars().nth() to get character safely

   The chars() iterator allows accessing the nth character safely with nth(2) and unwrap() to get the value.

3. Final Answer:

   let c = s.chars().nth(2).unwrap(); -> Option D

4. Quick Check:

   chars().nth(2).unwrap() = correct char access [OK]

Hint: Use chars().nth(index).unwrap() for safe char access [OK]

Common Mistakes:

• Using direct indexing like s[2]
• Using get(2) which returns Option<&str> slice, not char
• Using bytes() which returns u8, not char

3. What is the output of this Rust code?

let s = "rust";
let mut result = String::new();
for c in s.chars() {
    if c == 'u' {
        result.push('U');
    } else {
        result.push(c);
    }
}
println!("{}", result);

medium

A. rust

B. rUSt

C. rUst

D. Rust

Solution

1. Step 1: Iterate over each character in "rust"

   The loop goes over 'r', 'u', 's', 't' one by one.

2. Step 2: Replace 'u' with 'U' and keep others same

   When character is 'u', push 'U' to result; else push original char.

3. Final Answer:

   rUst -> Option C

4. Quick Check:

   Only 'u' replaced by 'U' = rUst [OK]

Hint: Check character equality and push accordingly [OK]

Common Mistakes:

• Replacing wrong characters
• Not pushing characters correctly
• Confusing uppercase and lowercase

4. Identify the error in this Rust code snippet:

let s = "hello";
let c = s[1];
println!("{}", c);

medium

A. s is not declared mutable

B. Cannot index string with integer directly

C. Missing semicolon after println!

D. println! macro syntax error

Solution

1. Step 1: Check string indexing rules in Rust

   Rust strings are UTF-8 encoded and do not support direct indexing by integer like arrays.

2. Step 2: Identify the invalid line

   The line let c = s[1]; causes a compile-time error because of invalid indexing.

3. Final Answer:

   Cannot index string with integer directly -> Option B

4. Quick Check:

   Direct indexing on String = error [OK]

Hint: Rust strings can't be indexed by integer directly [OK]

Common Mistakes:

• Assuming s[1] works like array indexing
• Ignoring UTF-8 encoding complexity
• Thinking semicolon or macro syntax is the error

5. Given a string s, how can you create a new string containing only the vowels from s in Rust?
Choose the correct code snippet.

hard

A. let vowels: String = s.chars().filter(|c| "aeiou".contains(*c)).collect();

B. let vowels: String = s.bytes().filter(|b| b == b'a' || b == b'e').collect();

C. let vowels: String = s.get(0..5).unwrap().to_string();

D. let vowels: String = s.chars().map(|c| if "aeiou".contains(c) { c } else { ' ' }).collect();

Solution

1. Step 1: Use chars() to iterate characters

   We need to check each character, so chars() is appropriate.

2. Step 2: Filter vowels and collect into String

   Filter characters that are vowels using filter and collect them into a new String.

3. Final Answer:

   let vowels: String = s.chars().filter(|c| "aeiou".contains(*c)).collect(); -> Option A

4. Quick Check:

   chars() + filter vowels + collect() = correct [OK]

Hint: Filter chars with contains("aeiou") and collect to String [OK]

Common Mistakes:

• Using bytes() which returns u8, not char
• Using get() which slices string, not filters vowels
• Replacing non-vowels with spaces instead of filtering