Iterating over strings in Python - Time & Space Complexity

Time Complexity: Iterating over strings

O(n)

Understanding Time Complexity

When we go through each letter in a word or sentence, we want to know how the time it takes grows as the word gets longer.

We ask: How does the work change when the string has more characters?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text = "hello world"
for char in text:
    print(char)
    
# This code prints each character in the string one by one.

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

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

Explain the growth pattern intuitively.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time it takes grows in a straight line with the length of the string.

Common Mistake

[X] Wrong: "Looping over a string is instant no matter how long it is."

[OK] Correct: Each character still needs to be looked at one by one, so longer strings take more time.

Interview Connect

Understanding how looping through strings scales helps you explain your code clearly and shows you know how programs handle data as it grows.

Self-Check

"What if we nested another loop inside to compare each character with every other character? How would the time complexity change?"

Practice

1. What does the following code do?
for letter in "hello":
print(letter)

easy

A. Prints each letter of the word 'hello' on a new line

B. Prints the whole word 'hello' once

C. Prints the length of the word 'hello'

D. Causes an error because strings can't be looped

Solution

1. Step 1: Understand the for loop over a string

   The loop goes through each character in the string "hello" one by one.

2. Step 2: Print each character

   Inside the loop, each letter is printed on its own line.

3. Final Answer:

   Prints each letter of the word 'hello' on a new line -> Option A

4. Quick Check:

   Loop over string prints letters individually [OK]

Hint: For loops over strings print letters one by one [OK]

Common Mistakes:

• Thinking the whole string prints at once
• Confusing string length with letters
• Believing strings can't be looped

2. Which of the following is the correct syntax to loop over each character in the string text?

easy

A. for char to text: print(char)

B. for char in range(text): print(char)

C. for char in text: print(char)

D. for i in text.length: print(i)

Solution

1. Step 1: Identify correct for loop syntax for strings

   In Python, to loop over characters in a string, use for variable in string:.

2. Step 2: Check each option

   for char in text:
print(char) uses correct syntax. The other options use invalid syntax like 'to' instead of 'in', range() on a string, or non-existent .length attribute.

3. Final Answer:

   for char in text:
   print(char) -> Option C

4. Quick Check:

   Correct for loop syntax over string is for char in text:
   print(char) [OK]

Hint: Use 'for char in string:' to loop letters [OK]

Common Mistakes:

• Using range() on a string directly
• Trying to use .length instead of len()
• Using incorrect loop keywords

3. What is the output of this code?

word = "code"
result = ""
for ch in word:
    result += ch.upper()
print(result)

medium

A. code

B. CODE

C. Code

D. cODe

Solution

1. Step 1: Loop through each letter in 'code'

   The loop takes each character: 'c', 'o', 'd', 'e'.

2. Step 2: Convert each letter to uppercase and add to result

   Each letter is changed to uppercase ('C', 'O', 'D', 'E') and added to the empty string result.

3. Final Answer:

   CODE -> Option B

4. Quick Check:

   Uppercase each letter and join = CODE [OK]

Hint: Uppercase letters inside loop to build new string [OK]

Common Mistakes:

• Not converting letters to uppercase
• Printing original string instead of result
• Using += without initializing result

4. Find the error in this code:

text = "hello"
for i in text:
    print(text[i])

medium

A. Variable 'text' is not defined

B. Missing colon after for loop

C. Loop should be 'for i in range(text):'

D. Using 'i' as index causes TypeError

Solution

1. Step 1: Understand the loop variable 'i'

   Here, 'i' takes each character from 'text', so 'i' is a letter, not an index.

2. Step 2: Using 'text[i]' causes error

   Since 'i' is a letter, using it as an index causes a TypeError because string indices must be integers.

3. Final Answer:

   Using 'i' as index causes TypeError -> Option D

4. Quick Check:

   Loop variable is letter, not index, so indexing fails [OK]

Hint: Loop variable is letter, not index; use range(len(text)) for indices [OK]

Common Mistakes:

• Assuming loop variable is index
• Trying to index string with a character
• Confusing loop variable with range

5. Write code to count how many vowels are in the string sentence. Which code correctly does this?

hard

A. count = 0
for ch in sentence:
if ch in 'aeiouAEIOU':
count += 1
print(count)

B. count = 0
for i in range(len(sentence)):
if sentence[i] == 'aeiou':
count += 1
print(count)

C. count = 0
for ch in sentence:
if ch == 'a' or 'e' or 'i' or 'o' or 'u':
count += 1
print(count)

D. count = 0
for ch in sentence:
if ch in ['a','e','i','o','u']:
count = count + 1
print(count)

Solution

1. Step 1: Check vowel membership correctly

   count = 0 for ch in sentence: if ch in 'aeiouAEIOU': count += 1 print(count) checks if each character is in the string of vowels (both lowercase and uppercase), which is correct.

2. Step 2: Verify counting logic

   count = 0 for ch in sentence: if ch in 'aeiouAEIOU': count += 1 print(count) increments count correctly when a vowel is found and prints the total count.

3. Final Answer:

   count = 0 for ch in sentence: if ch in 'aeiouAEIOU': count += 1 print(count) -> Option A

4. Quick Check:

   Use 'in' with vowel string and increment count [OK]

Hint: Use 'if ch in "aeiouAEIOU"' to check vowels [OK]

Common Mistakes:

• Using '==' to compare with multiple vowels
• Checking membership incorrectly with list without uppercase
• Not incrementing count properly