String Traversal and Character Access in DSA Rust - Time & Space Complexity

Time Complexity: String Traversal and Character Access

O(n)

Understanding Time Complexity

We want to know how long it takes to look at each letter in a word or sentence.

How does the time grow when the string gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn print_chars(s: &str) {
    for c in s.chars() {
        println!("{}", c);
    }
}

This code goes through each character in a string and prints it one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each character in the string.
• How many times: Once for every character in the string.

How Execution Grows With Input

As the string gets longer, the number of steps grows in a straight line with the number of characters.

Input Size (n)	Approx. Operations
10	10
100	100
1000	1000

Pattern observation: Doubling the string length doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows directly with the string length.

Common Mistake

[X] Wrong: "Accessing each character is instant and does not depend on string length."

[OK] Correct: Each character must be visited one by one, so time grows with string size.

Interview Connect

Understanding how string length affects processing time helps you explain your code clearly and shows you know how to handle data efficiently.

Self-Check

"What if we used indexing to access characters instead of iterating? How would the time complexity change?"

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