String Traversal and Character Access in DSA Typescript - 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 grow when the word gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function printChars(str: string): void {
  for (let i = 0; i < str.length; i++) {
    console.log(str[i]);
  }
}
    

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing each character in the string inside the 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 and prints
100	100 character accesses and prints
1000	1000 character accesses and prints

Pattern observation: The work grows directly with the length of the string.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Accessing characters inside a string is instant and does not add to time."

[OK] Correct: Each character access happens one by one, so more characters mean more time.

Interview Connect

Knowing how string traversal time grows helps you explain how your code handles longer inputs clearly and confidently.

Self-Check

"What if we used two nested loops to compare every character with every other character? How would the time complexity change?"

Practice

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

easy

A. The character 'e'

B. The character 'l'

C. The substring 'll'

D. An error because strings are not indexable

Solution

1. Step 1: Understand string indexing

   Strings in TypeScript can be accessed by index starting at 0, so index 2 refers to the third character.

2. Step 2: Identify the character at index 2 in "hello"

   The characters are: h(0), e(1), l(2), l(3), o(4). So index 2 is 'l'.

3. Final Answer:

   The character 'l' -> Option B

4. Quick Check:

   str[2] = 'l' [OK]

Hint: Remember string index starts at 0 [OK]

Common Mistakes:

• Thinking index starts at 1
• Confusing character with substring
• Assuming strings are not indexable

2. Which of the following is the correct way to loop through each character of a string text in TypeScript?

easy

A. for (let char of text) { console.log(char); }

B. for (let char in text) { console.log(char); }

C. for (let i = 0; i <= text.length; i++) { console.log(text[i]); }

D. for (let i = 1; i <= text.length; i++) { console.log(text[i]); }

Solution

1. Step 1: Understand looping over strings

   Using for...of loops over characters directly, which is the cleanest way.

2. Step 2: Evaluate the options

   The index-based loop using <= text.length causes an out-of-bounds access. for...in iterates over string indices ('0', '1', etc.) rather than characters. for...of correctly iterates over characters. Starting the index at 1 skips the first character and risks out-of-bounds.

3. Final Answer:

   for (let char of text) { console.log(char); } -> Option A

4. Quick Check:

   Use for...of to access characters directly [OK]

Hint: Use for...of to loop characters directly [OK]

Common Mistakes:

• Using for...in which loops keys, not values
• Starting index at 1 instead of 0
• Confusing index with character in loops

3. What is the output of the following code?

const s = "abcde";
let result = "";
for (let i = 0; i < s.length; i += 2) {
  result += s[i];
}
console.log(result);

medium

A. "bdf"

B. ""

C. "abcde"

D. "ace"

Solution

1. Step 1: Analyze the loop increments and indexing

   The loop starts at 0 and increments by 2 each time, so indexes are 0, 2, 4.

2. Step 2: Collect characters at indexes 0, 2, 4

   Characters are s[0] = 'a', s[2] = 'c', s[4] = 'e'. Concatenated result is "ace".

3. Final Answer:

   "ace" -> Option D

4. Quick Check:

   Indexes 0,2,4 characters combined = "ace" [OK]

Hint: Check loop step size and indexes accessed [OK]

Common Mistakes:

• Assuming loop increments by 1
• Confusing indexes with characters
• Expecting all characters concatenated

4. Identify the error in the following code snippet that tries to print each character of word:

const word = "test";
for (let i = 1; i <= word.length; i++) {
  console.log(word[i]);
}

medium

A. Missing declaration of variable i

B. Using <= instead of < causes infinite loop

C. Indexing starts at 1, skipping first character and causing undefined at end

D. Strings cannot be accessed by index in TypeScript

Solution

1. Step 1: Check loop index range

   The loop starts at 1 and goes up to word.length (4), so indexes accessed are 1,2,3,4.

2. Step 2: Identify indexing issues

   Index 0 is skipped (first character 't'), and index 4 is out of bounds (undefined). So first character is missed and last access is invalid.

3. Final Answer:

   Indexing starts at 1, skipping first character and causing undefined at end -> Option C

4. Quick Check:

   String indexes start at 0, not 1 [OK]

Hint: Loop indexes for strings start at 0 and go to length-1 [OK]

Common Mistakes:

• Starting loop at 1 instead of 0
• Using <= instead of < in loop condition
• Assuming strings are not indexable

5. Given a string input, which code snippet correctly reverses the string by traversing it from end to start?

hard

A. let rev = '';
for (let i = input.length - 1; i >= 0; i--) {
rev += input[i];
}
console.log(rev);

B. let rev = '';
for (let i = 0; i < input.length; i++) {
rev += input[input.length - i];
}
console.log(rev);

C. let rev = '';
for (let i = input.length; i > 0; i--) {
rev += input[i];
}
console.log(rev);

D. let rev = '';
for (let i = input.length; i >= 0; i--) {
rev += input[i];
}
console.log(rev);

Solution

1. Step 1: Understand correct index range for reverse traversal

   Indexes go from input.length - 1 down to 0 inclusive to cover all characters in reverse.

2. Step 2: Verify the index ranges

   Looping from input.length - 1 down to 0 inclusive correctly captures all characters in reverse. A forward loop using input.length - i first accesses an out-of-bounds index. Starting at input.length immediately accesses invalid index. Decrementing from input.length to 0 also starts with out-of-bounds.

3. Final Answer:

   let rev = ''; for (let i = input.length - 1; i >= 0; i--) { rev += input[i]; } console.log(rev); -> Option A

4. Quick Check:

   Loop from length-1 down to 0 for reverse traversal [OK]

Hint: Start loop at length-1 and go down to 0 [OK]

Common Mistakes:

• Starting loop at length instead of length-1
• Using wrong index inside loop causing undefined
• Loop condition off by one causing missing characters