String length and membership test in Python - Time & Space Complexity

Time Complexity: String length and membership test

O(n)

Understanding Time Complexity

We want to understand how long it takes to check the length of a string and to see if a character is inside it.

How does the time needed change when the string gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

my_string = "hello world"
length = len(my_string)
if 'w' in my_string:
    print("Found 'w'!")
else:
    print("'w' not found.")

This code gets the length of a string and checks if the letter 'w' is inside it.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each character to find 'w' in the string.
• How many times: Up to once for each character until 'w' is found or the end is reached.

How Execution Grows With Input

As the string gets longer, checking for 'w' may take longer because it might look at more characters.

Input Size (n)	Approx. Operations
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

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

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Checking if a character is in a string always takes the same time, no matter the string size."

[OK] Correct: The check may need to look at many characters, so longer strings usually take more time.

Interview Connect

Knowing how string operations grow with size helps you write clear and efficient code, a skill that shows your understanding of how programs work behind the scenes.

Self-Check

"What if we checked for a substring instead of a single character? How would the time complexity change?"

Practice

1.

What does the expression len('hello') return in Python?

easy

A. 5

B. 'hello'

C. 4

D. Error

Solution

1. Step 1: Understand the len() function

   The len() function counts how many characters are in a string.

2. Step 2: Count characters in 'hello'

   The word 'hello' has 5 letters: h, e, l, l, o.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   len('hello') = 5 [OK]

Hint: Count letters to find length quickly [OK]

Common Mistakes:

• Counting letters incorrectly
• Confusing len() with printing string
• Expecting len() to return string itself

2.

Which of the following is the correct syntax to check if the letter 'a' is in the string word?

easy

A. word.contains('a')

B. word in 'a'

C. in 'a' word

D. 'a' in word

Solution

1. Step 1: Recall Python membership syntax

   To check if a substring is inside a string, use substring in string.

2. Step 2: Apply to letter 'a' and variable word

   We write 'a' in word to check if 'a' is inside word.

3. Final Answer:

   'a' in word -> Option D

4. Quick Check:

   Use 'in' as: substring in string [OK]

Hint: Use 'in' with substring first, then string [OK]

Common Mistakes:

• Reversing order of 'in'
• Using non-Python syntax like contains()
• Syntax errors with 'in' placement

3.

What is the output of this code?

word = 'python'
print(len(word) > 5 and 'y' in word)

medium

A. False

B. 6

C. True

D. Error

Solution

1. Step 1: Calculate len(word)

   The string 'python' has 6 characters, so len(word) is 6.

2. Step 2: Evaluate conditions

   Check if 6 > 5 (True) and if 'y' is in 'python' (True). Both are True, so the whole expression is True.

3. Final Answer:

   True -> Option C

4. Quick Check:

   len(word)>5 and 'y' in word = True [OK]

Hint: Check length first, then membership with 'and' [OK]

Common Mistakes:

• Confusing > with >= operator
• Forgetting 'and' logic
• Miscounting string length

4.

Find the error in this code snippet:

text = 'apple'
if 'p' not in text:
    print('No p found')
else
    print('p is present')

medium

A. Missing colon ':' after else

B. Wrong use of 'not in' operator

C. Variable 'text' is not defined

D. Indentation error on print statements

Solution

1. Step 1: Check syntax of if-else

   Python requires a colon ':' after both if and else statements.

2. Step 2: Identify missing colon

   The else line is missing a colon at the end, causing a syntax error.

3. Final Answer:

   Missing colon ':' after else -> Option A

4. Quick Check:

   else: needs colon [OK]

Hint: Always put ':' after else and if lines [OK]

Common Mistakes:

• Omitting colon after else
• Misusing 'not in' operator
• Incorrect indentation

5.

Given a list of words, write a Python expression to create a new list containing only words longer than 4 characters and containing the letter 'e'.

Which of these is correct?

hard

A. [w for w in words if len(w) > 4 or 'e' in w]

B. [w for w in words if len(w) > 4 and 'e' in w]

C. [w for w in words if len(w) >= 4 and 'e' not in w]

D. [w for w in words if len(w) < 4 or 'e' not in w]

Solution

1. Step 1: Understand the conditions

   We want words longer than 4 characters and that contain 'e'. This means length > 4 and 'e' in word.

2. Step 2: Check list comprehension syntax

   The correct syntax is [w for w in words if len(w) > 4 and 'e' in w] which filters words by both conditions.

3. Final Answer:

   [w for w in words if len(w) > 4 and 'e' in w] -> Option B

4. Quick Check:

   Filter with len()>4 and 'e' in word [OK]

Hint: Use 'and' to combine length and membership tests [OK]

Common Mistakes:

• Using 'or' instead of 'and'
• Wrong comparison operators
• Negating membership incorrectly