String Reversal Approaches in DSA Rust

Mental Model

Reversing a string means flipping its characters so the last becomes first and the first becomes last.

Analogy: Imagine reading a sentence backwards, starting from the end and moving to the beginning, like rewinding a tape.

Original: H -> e -> l -> l -> o -> null
Reversed: o -> l -> l -> e -> H -> null

Dry Run Walkthrough

Input: string: "hello"

Goal: Reverse the string so it reads "olleh"

Step 1: Start with two pointers: left at 'h' (index 0), right at 'o' (index 4)

h [left] -> e -> l -> l -> o [right] -> null

Why: We need to swap characters from both ends moving towards the center

Step 2: Swap characters at left and right: 'h' and 'o'

o -> e -> l -> l -> h -> null

Why: Swapping first and last characters moves them to their reversed positions

Step 3: Move left pointer to 'e' (index 1), right pointer to 'l' (index 3)

o -> e [left] -> l -> l [right] -> h -> null

Why: Continue swapping inward characters

Step 4: Swap characters at left and right: 'e' and 'l'

o -> l -> l -> e -> h -> null

Why: Swapping these characters continues the reversal

Step 5: Move left pointer to 'l' (index 2), right pointer to 'l' (index 2)

o -> l -> l [left,right] -> e -> h -> null

Why: Pointers meet at the middle, no more swaps needed

Result:

o -> l -> l -> e -> h -> null
Reversed string: "olleh"

Annotated Code

DSA Rust

fn reverse_string(s: &mut [char]) {
    let mut left = 0;
    let mut right = s.len().saturating_sub(1);
    while left < right {
        s.swap(left, right); // swap characters at left and right
        left += 1; // move left pointer rightwards
        right = right.saturating_sub(1); // move right pointer leftwards
    }
}

fn main() {
    let mut chars: Vec<char> = "hello".chars().collect();
    reverse_string(&mut chars);
    let reversed: String = chars.into_iter().collect();
    println!("{}", reversed);
}

while left < right {

loop until pointers meet or cross to cover all swaps

s.swap(left, right); // swap characters at left and right

exchange characters at current pointers to reverse positions

left += 1; // move left pointer rightwards

advance left pointer inward

right = right.saturating_sub(1); // move right pointer leftwards

move right pointer inward safely

Output

olleh

Complexity Analysis

Time: O(n) because we swap characters from both ends moving towards the center, covering all n characters once

Space: O(1) because reversal is done in place without extra storage

vs Alternative: Compared to creating a new reversed string (O(n) time and space), this in-place method saves memory by modifying the original string

Edge Cases

empty string

function returns immediately with no changes

DSA Rust

while left < right {

single character string

no swaps occur since left is not less than right

DSA Rust

while left < right {

string with repeated characters

characters swap normally, result is reversed string with duplicates preserved

DSA Rust

s.swap(left, right); // swap characters at left and right

When to Use This Pattern

When you need to reverse a sequence of characters efficiently, use the two-pointer swap approach because it reverses in place with minimal extra space.

Common Mistakes

Mistake: Using a loop that goes from start to end without stopping at the middle, causing double swaps and returning original string
Fix: Stop the loop when left pointer meets or passes right pointer to avoid undoing swaps

Summary

Reverses a string by swapping characters from both ends moving inward.

Use when you want to reverse a string efficiently without extra memory.

The key is to swap pairs of characters moving inward until pointers meet.

Practice

1. What does the chars().rev().collect() method chain do when applied to a Rust string?

easy

A. It reverses the characters of the string and collects them into a new string.

B. It sorts the characters of the string in ascending order.

C. It removes all whitespace characters from the string.

D. It converts the string to uppercase.

Solution

1. Step 1: Understand chars() method

   The chars() method converts the string into an iterator over its characters.

2. Step 2: Apply rev() and collect()

   The rev() method reverses the iterator, and collect() gathers the reversed characters into a new string.

3. Final Answer:

   It reverses the characters of the string and collects them into a new string. -> Option A

4. Quick Check:

   chars().rev().collect() reverses string [OK]

Hint: Remember: chars() + rev() + collect() reverses a string [OK]

Common Mistakes:

• Thinking it sorts characters instead of reversing
• Confusing rev() with removing characters
• Assuming it changes case of letters

2. Which of the following Rust code snippets correctly reverses a string s?

easy

A. let reversed: String = s.reverse();

B. let reversed: String = s.chars().rev().collect();

C. let reversed: String = s.collect().rev().chars();

D. let reversed: String = s.chars().collect().rev();

Solution

1. Step 1: Check method availability

   Rust strings do not have a reverse() method, so let reversed: String = s.reverse(); is invalid.

2. Step 2: Analyze method chaining

   let reversed: String = s.chars().rev().collect(); uses chars() to get characters, rev() to reverse, and collect() to form a new string, which is correct.

3. Final Answer:

   let reversed: String = s.chars().rev().collect(); -> Option B

4. Quick Check:

   Correct syntax for string reversal is let reversed: String = s.chars().rev().collect(); [OK]

Hint: Use chars().rev().collect() to reverse strings in Rust [OK]

Common Mistakes:

• Using non-existent reverse() method on String
• Wrong order of method calls
• Trying to reverse after collecting into String

3. What is the output of the following Rust code?

let s = String::from("rust");
let reversed: String = s.chars().rev().collect();
println!("{}", reversed);

medium

A. Error: cannot reverse string

B. rust

C. tsur

D. tusr

Solution

1. Step 1: Understand input string

   The string "rust" has characters 'r', 'u', 's', 't'.

2. Step 2: Reverse characters and collect

   Using chars().rev().collect() reverses the characters to 't', 's', 'u', 'r' and collects into a new string.

3. Final Answer:

   tsur -> Option C

4. Quick Check:

   Reversed "rust" = "tsur" [OK]

Hint: Trace chars().rev().collect() to get reversed string output [OK]

Common Mistakes:

• Expecting original string output
• Mixing character order incorrectly
• Assuming runtime error on reversal

4. Identify the error in this Rust code that attempts to reverse a string:

let s = String::from("hello");
let reversed = s.reverse();
println!("{}", reversed);

medium

A. reverse() returns a vector, not a string

B. Missing semicolon after println! macro

C. Cannot print reversed string directly

D. String type has no method named reverse()

Solution

1. Step 1: Check method existence on String

   Rust's String type does not have a reverse() method, so calling it causes a compile error.

2. Step 2: Confirm other syntax correctness

   The semicolon after println! is present, and printing a string is valid, so no errors there.

3. Final Answer:

   String type has no method named reverse() -> Option D

4. Quick Check:

   reverse() method does not exist on String [OK]

Hint: Remember: String has no reverse() method in Rust [OK]

Common Mistakes:

• Assuming reverse() exists on String
• Thinking reverse() returns vector automatically
• Ignoring compiler error messages

5. You want to reverse a string but keep all Unicode grapheme clusters intact (like emojis or accented letters). Which Rust crate and approach is best suited for this?

hard

A. Use the unicode-segmentation crate to split by graphemes, then reverse and collect.

B. Use chars().rev().collect() directly on the string.

C. Convert string to bytes, reverse bytes, then convert back to string.

D. Use split_whitespace() and reverse the words.

Solution

1. Step 1: Understand Unicode grapheme clusters

   Some characters like emojis or accented letters are multiple Unicode code points but one visible character (grapheme cluster).

2. Step 2: Use appropriate crate and method

   The unicode-segmentation crate provides graphemes() method to split string by grapheme clusters, which can then be reversed safely.

3. Final Answer:

   Use the unicode-segmentation crate to split by graphemes, then reverse and collect. -> Option A

4. Quick Check:

   unicode-segmentation crate handles grapheme reversal correctly [OK]

Hint: Use unicode-segmentation crate for correct Unicode string reversal [OK]

Common Mistakes:

• Reversing by chars() breaks multi-codepoint characters
• Reversing bytes corrupts UTF-8 encoding
• Reversing words instead of characters