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

Time Complexity: String Traversal and Character Access

O(n)

Understanding Time Complexity

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

How does the time needed change when the word gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

string text = "hello world";
for (int i = 0; i < text.Length; i++)
{
    char c = text[i];
    // process character c
}
    

This code goes through each letter in the string one by one.

Identify Repeating Operations

• Primary operation: Accessing each character in the string using a loop.
• 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 the same way.

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

Pattern observation: The work grows directly with the number of characters.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows in a straight line as the string gets longer.

Common Mistake

[X] Wrong: "Accessing characters inside a string is instant no matter the size."

[OK] Correct: Even though each access is quick, doing it for every character adds up as the string grows.

Interview Connect

Knowing how string traversal time grows helps you explain your code's speed clearly and confidently.

Self-Check

"What if we only checked every other character instead of every character? How would the time complexity change?"

Practice

1. What does the expression str[2] return when string str = "hello";?

easy

A. The character 'o'

B. The character 'l'

C. The character 'e'

D. An error because strings cannot be indexed

Solution

1. Step 1: Understand zero-based indexing in strings

   In C#, string characters are accessed starting from index 0. So, str[0] = 'h', str[1] = 'e', str[2] = 'l'.

2. Step 2: Identify the character at index 2

   The character at index 2 in "hello" is 'l'.

3. Final Answer:

   The character 'l' -> Option B

4. Quick Check:

   str[2] = 'l' [OK]

Hint: Remember string indexing starts at 0 in C# [OK]

Common Mistakes:

• Thinking indexing starts at 1
• Confusing characters at index 1 and 2
• Assuming strings can't be indexed

2. Which of the following is the correct way to loop through each character in a string str in C#?

easy

A. for (char c = 0; c < str.Length; c++) { Console.WriteLine(str[c]); }

B. for (int i = 1; i <= str.Length; i++) { Console.WriteLine(str[i]); }

C. foreach (int c in str) { Console.WriteLine(c); }

D. for (int i = 0; i < str.Length; i++) { Console.WriteLine(str[i]); }

Solution

1. Step 1: Check loop indexing and range

   In C#, string indexing starts at 0 and goes up to Length - 1. So the loop must run from 0 to str.Length - 1.

2. Step 2: Validate each option

   for (int i = 0; i < str.Length; i++) { Console.WriteLine(str[i]); } uses correct indexing (0 to Length-1). for (int i = 1; i <= str.Length; i++) { Console.WriteLine(str[i]); } starts at 1 and uses <= which causes out-of-range error. foreach (int c in str) { Console.WriteLine(c); } tries to foreach over int, but string yields chars, so type mismatch. for (char c = 0; c < str.Length; c++) { Console.WriteLine(str[c]); } uses char as loop variable which is incorrect.

3. Final Answer:

   for (int i = 0; i < str.Length; i++) { Console.WriteLine(str[i]); } -> Option D

4. Quick Check:

   Loop from 0 to Length-1 for string traversal [OK]

Hint: Use for loop with i from 0 to str.Length - 1 [OK]

Common Mistakes:

• Starting loop at 1 instead of 0
• Using <= instead of < in loop condition
• Using wrong variable type in foreach

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

string s = "code";
for (int i = 0; i < s.Length; i++)
{
    if (i % 2 == 0)
        Console.Write(s[i]);
}

medium

A. co

B. oe

C. cd

D. code

Solution

1. Step 1: Understand the loop and condition

   The loop runs from i=0 to i=3 (length 4). It prints characters only when i is even (0, 2).

2. Step 2: Identify characters at even indices

   At i=0, s[0] = 'c'; at i=2, s[2] = 'd'. So output is "cd".

3. Final Answer:

   cd -> Option C

4. Quick Check:

   Print chars at even indices: 'c' and 'd' [OK]

Hint: Print characters where index % 2 == 0 [OK]

Common Mistakes:

• Confusing even and odd indices
• Printing all characters ignoring condition
• Misreading string length

4. Identify the error in the following code snippet:

string text = "example";
for (int i = 0; i <= text.Length; i++)
{
    Console.Write(text[i]);
}

medium

A. The loop condition should be < instead of <=

B. The string cannot be indexed with []

C. Variable i should be of type char

D. Console.Write should be Console.WriteLine

Solution

1. Step 1: Analyze loop condition and indexing

   The loop runs from i=0 to i <= text.Length. Since string indices go from 0 to Length-1, accessing text[Length] causes an error.

2. Step 2: Correct the loop condition

   Change condition to i < text.Length to avoid out-of-range exception.

3. Final Answer:

   The loop condition should be < instead of <= -> Option A

4. Quick Check:

   Loop must run from 0 to Length-1 [OK]

Hint: Use i < str.Length to avoid index out of range [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Assuming string indexing is 1-based
• Changing variable type unnecessarily

5. Given a string input, which code snippet correctly counts how many vowels (a, e, i, o, u) it contains?

hard

A. int count = 0;
foreach (char c in input.ToLower()) {
if ("aeiou".Contains(c)) count++;
}
Console.WriteLine(count);

B. int count = 0;
for (int i = 1; i <= input.Length; i++) {
if ("aeiou".Contains(input[i])) count++;
}
Console.WriteLine(count);

C. int count = 0;
foreach (int c in input) {
if ("aeiou".Contains((char)c)) count++;
}
Console.WriteLine(count);

D. int count = 0;
for (char c = 0; c < input.Length; c++) {
if ("aeiou".Contains(input[c])) count++;
}
Console.WriteLine(count);

Solution

1. Step 1: Check correct iteration over string characters

   int count = 0; foreach (char c in input.ToLower()) { if ("aeiou".Contains(c)) count++; } Console.WriteLine(count); uses foreach over chars in input.ToLower(), which is correct. int count = 0; for (int i = 1; i <= input.Length; i++) { if ("aeiou".Contains(input[i])) count++; } Console.WriteLine(count); uses 1-based indexing causing out-of-range error. int count = 0; foreach (int c in input) { if ("aeiou".Contains((char)c)) count++; } Console.WriteLine(count); uses foreach over int which is incorrect type. int count = 0; for (char c = 0; c < input.Length; c++) { if ("aeiou".Contains(input[c])) count++; } Console.WriteLine(count); uses char as loop variable which is invalid.

2. Step 2: Verify vowel check and counting

   int count = 0; foreach (char c in input.ToLower()) { if ("aeiou".Contains(c)) count++; } Console.WriteLine(count); checks if character is in "aeiou" string and increments count correctly.

3. Final Answer:

   Option A code snippet correctly counts vowels -> Option A

4. Quick Check:

   Use foreach char and check vowels with Contains [OK]

Hint: Use foreach char in lowercase string and Contains("aeiou") [OK]

Common Mistakes:

• Using wrong loop indices causing errors
• Incorrect variable types in loops
• Not converting string to lowercase before checking