Character type in Rust - Time & Space Complexity

Time Complexity: Character type

O(n)

Understanding Time Complexity

When working with characters in Rust, it's important to understand how operations on them scale as input grows.

We want to know how the time to process characters changes when we handle more of them.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn count_vowels(text: &str) -> usize {
    let mut count = 0;
    for ch in text.chars() {
        if matches!(ch, 'a' | 'e' | 'i' | 'o' | 'u' |
                         'A' | 'E' | 'I' | 'O' | 'U') {
            count += 1;
        }
    }
    count
}

This function counts how many vowels are in a given text string by checking each character.

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 input text.

How Execution Grows With Input

As the text gets longer, the function checks more characters one by one.

Input Size (n)	Approx. Operations
10	About 10 character checks
100	About 100 character checks
1000	About 1000 character checks

Pattern observation: The work grows directly with the number of characters; double the text, double the checks.

Final Time Complexity

Time Complexity: O(n)

This means the time to count vowels grows in a straight line with the length of the input text.

Common Mistake

[X] Wrong: "Checking each character is constant time no matter how long the text is."

[OK] Correct: Actually, the function must look at every character, so more characters mean more work.

Interview Connect

Understanding how character processing scales helps you write efficient text handling code, a common task in many programs.

Self-Check

"What if we changed the function to count vowels only in the first half of the text? How would the time complexity change?"

Practice

1. Which of the following correctly declares a char variable in Rust?

easy

A. let letter: char = `a`;

B. let letter: char = 'a';

C. let letter: char = a;

D. let letter: char = "a";

Solution

1. Step 1: Understand Rust char syntax

   Rust uses single quotes for char literals, e.g., 'a'. Double quotes are for strings.

2. Step 2: Check each option

   let letter: char = 'a'; uses single quotes correctly. let letter: char = "a"; uses double quotes (string). let letter: char = a; misses quotes. let letter: char = `a`; uses backticks, which is invalid.

3. Final Answer:

   let letter: char = 'a'; -> Option B

4. Quick Check:

   char uses single quotes [OK]

Hint: Remember: single quotes for char, double quotes for string [OK]

Common Mistakes:

• Using double quotes instead of single quotes
• Omitting quotes around the character
• Using backticks instead of quotes

2. Which of the following is the correct way to assign the emoji 😀 to a char variable in Rust?

easy

A. let smiley: char = '😀';

B. let smiley: char = 😀;

C. let smiley: char = "😀";

D. let smiley: char = `😀`;

Solution

1. Step 1: Recall char literal rules

   Rust char literals must be in single quotes, even for emojis.

2. Step 2: Evaluate options

   let smiley: char = '😀'; uses single quotes correctly with the emoji. Double quotes ("😀") create a string. Bare 😀 lacks quotes. Backticks (`😀`) are invalid.

3. Final Answer:

   let smiley: char = '😀'; -> Option A

4. Quick Check:

   Emoji char uses single quotes [OK]

Hint: Use single quotes for any char, including emojis [OK]

Common Mistakes:

• Using double quotes for char
• Not quoting the emoji
• Using backticks instead of single quotes

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

let c: char = 'Z';
println!("{}", c.is_alphabetic());

medium

A. true

B. false

C. Z

D. Compile error

Solution

1. Step 1: Understand is_alphabetic() method

   This method returns true if the char is a letter (A-Z or a-z or other alphabets).

2. Step 2: Check the character 'Z'

   'Z' is an uppercase letter, so is_alphabetic() returns true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   'Z'.is_alphabetic() = true [OK]

Hint: Check if char is letter with is_alphabetic() method [OK]

Common Mistakes:

• Confusing output with printing the char itself
• Thinking is_alphabetic() returns the char
• Expecting a compile error

4. Identify the error in this Rust code snippet:

let ch: char = 'ab';

medium

A. Missing semicolon at the end

B. Use double quotes for multiple characters

C. char type cannot store letters

D. Multiple characters in single quotes are not allowed

Solution

1. Step 1: Check char literal rules

   A char can only hold one Unicode character, so 'ab' is invalid.

2. Step 2: Analyze the error

   Using multiple characters inside single quotes causes a compile error.

3. Final Answer:

   Multiple characters in single quotes are not allowed -> Option D

4. Quick Check:

   char holds one char only [OK]

Hint: char must be one character in single quotes [OK]

Common Mistakes:

• Trying to store multiple characters in a char
• Using double quotes for char
• Ignoring compile errors

5. Given a string slice let s = "Rust 🦀";, which Rust code correctly extracts the crab emoji as a char?

hard

A. let crab = s.chars().nth(4).unwrap();

B. let crab = s[5];

C. let crab = s.chars().nth(5).unwrap();

D. let crab = s[4..5].chars().next().unwrap();

Solution

1. Step 1: Understand string and char indexing in Rust

   Rust strings are UTF-8 encoded. The string "Rust 🦀" has 6 chars: 'R'(0),'u'(1),'s'(2),'t'(3),' '(4),'🦀'(5). Crab emoji is the 6th character (index 5), counting chars, not bytes.

2. Step 2: Check each option

   let crab = s.chars().nth(5).unwrap(); correctly uses chars().nth(5) to get the crab emoji. let crab = s.chars().nth(4).unwrap(); gets the space (index 4). let crab = s[5]; uses byte index (u8, not char). let crab = s[4..5].chars().next().unwrap(); byte slice yields space.

3. Final Answer:

   let crab = s.chars().nth(5).unwrap(); -> Option C

4. Quick Check:

   Use chars().nth(5) for crab emoji [OK]

Hint: Use chars().nth(index) to get char by position [OK]

Common Mistakes:

• Indexing string bytes directly
• Using wrong index for emoji
• Not unwrapping Option from nth()