String Reversal Approaches in DSA Python - Time & Space Complexity

Time Complexity: String Reversal Approaches

O(n^2)

Understanding Time Complexity

We want to understand how the time needed to reverse a string changes as the string gets longer.

How does the work grow when the input string size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def reverse_string(s: str) -> str:
    result = []
    for char in s:
        result.insert(0, char)
    return ''.join(result)

This code reverses a string by inserting each character at the start of a list, then joining the list into a string.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping over each character in the string and inserting it at the start of the list.
• How many times: Once for each character in the string (n times).

How Execution Grows With Input

Each insertion at the start shifts existing elements, so work grows faster than just the number of characters.

Input Size (n)	Approx. Operations
10	About 55 (sum of 1 to 10)
100	About 5,050
1000	About 500,500

Pattern observation: Operations grow roughly with the square of the input size.

Final Time Complexity

Time Complexity: O(n2)

This means the time needed grows roughly with the square of the string length because each insert shifts elements.

Common Mistake

[X] Wrong: "Inserting at the start of a list is a quick, constant-time operation like appending at the end."

[OK] Correct: Inserting at the start requires moving all existing elements one step, so it takes longer as the list grows.

Interview Connect

Understanding how different ways to reverse a string affect time helps you choose the best method in real problems.

Self-Check

"What if we used a list to collect characters by appending at the end and then reversed the list once at the end? How would the time complexity change?"

Practice

1. Which of the following methods correctly reverses a string s in Python?

easy

A. Using reversed(s) without converting to string

B. Using slicing: s[::-1]

C. Using s.reverse() method

D. Using s.append() method

Solution

1. Step 1: Understand string slicing

   The slicing syntax s[::-1] creates a new string with characters in reverse order.

2. Step 2: Check other methods

   s.reverse() and s.append() are list methods, not valid for strings. reversed(s) returns an iterator, not a string, so it needs conversion.

3. Final Answer:

   Using slicing: s[::-1] -> Option B

4. Quick Check:

   String slicing with negative step reverses string [OK]

Hint: Use s[::-1] to reverse strings quickly [OK]

Common Mistakes:

• Trying to use list methods on strings
• Forgetting to convert reversed() iterator to string
• Using append() on strings

2. Which of the following code snippets correctly reverses the string text = 'hello' and prints it?

easy

A. print(text.append('o'))

B. print(text.reverse())

C. print(text[::-2])

D. print(''.join(reversed(text)))

Solution

1. Step 1: Analyze each option

   text.reverse() is invalid for strings. text[::-2] reverses with step 2, skipping characters. text.append() is invalid for strings.

2. Step 2: Confirm correct syntax

   reversed(text) returns an iterator of characters reversed. ''.join() converts it back to string. This prints 'olleh'.

3. Final Answer:

   print(''.join(reversed(text))) -> Option D

4. Quick Check:

   reversed() + join() prints reversed string [OK]

Hint: Use ''.join(reversed(s)) to reverse strings [OK]

Common Mistakes:

• Using reverse() method on strings
• Using slicing with wrong step
• Trying to append to strings

3. What is the output of the following code?

def reverse_string(s):
    result = ''
    for char in s:
        result = char + result
    return result

print(reverse_string('abc'))

medium

A. 'cba'

B. 'abc'

C. 'bac'

D. Error

Solution

1. Step 1: Trace the loop for s='abc'

   Initially, result = ''. Iteration 1: char='a', result='a' + '' = 'a'. Iteration 2: char='b', result='b' + 'a' = 'ba'. Iteration 3: char='c', result='c' + 'ba' = 'cba'.

2. Step 2: Return the reversed string

   The function returns 'cba', which is the reverse of 'abc'.

3. Final Answer:

   'cba' -> Option A

4. Quick Check:

   Prepending chars reverses string [OK]

Hint: Add each char before result to reverse string [OK]

Common Mistakes:

• Appending char instead of prepending
• Returning original string
• Confusing order of concatenation

4. The following code is intended to reverse a string but has an error. What is the error?

def reverse_str(s):
    s.reverse()
    return s

print(reverse_str('hello'))

medium

A. Missing return statement

B. Function returns None

C. Strings do not have reverse() method

D. Syntax error in function definition

Solution

1. Step 1: Check method usage on string

   The reverse() method exists for lists, not strings. Calling it on a string causes AttributeError.

2. Step 2: Understand the error cause

   Since strings are immutable, they do not support reverse(). The code will raise an error at runtime.

3. Final Answer:

   Strings do not have reverse() method -> Option C

4. Quick Check:

   reverse() is list method, not string method [OK]

Hint: Use slicing or reversed() for strings, not reverse() [OK]

Common Mistakes:

• Trying to use reverse() on strings
• Expecting reverse() to modify string in place
• Ignoring immutability of strings

5. You want to reverse only the vowels in a string s = 'hello world' while keeping other characters in place. Which approach below correctly achieves this?

hard

A. Extract vowels, reverse them, then replace vowels in original positions

B. Reverse entire string using s[::-1]

C. Use reversed(s) and join all characters

D. Replace vowels with '*' and then reverse string

Solution

1. Step 1: Understand the problem

   We want to reverse only vowels, keeping consonants and spaces fixed in their places.

2. Step 2: Analyze each option

   Reverse entire string using s[::-1] reverses whole string, changing all characters. Use reversed(s) and join all characters reverses all characters, not just vowels. Replace vowels with '*' and then reverse string replaces vowels with '*', losing original vowels. Extract vowels, reverse them, then replace vowels in original positions extracts vowels, reverses them, then puts them back in original vowel positions, preserving other characters.

3. Final Answer:

   Extract vowels, reverse them, then replace vowels in original positions -> Option A

4. Quick Check:

   Reverse vowels only by extracting and replacing [OK]

Hint: Extract vowels, reverse, then put back in place [OK]

Common Mistakes:

• Reversing entire string instead of vowels only
• Replacing vowels with placeholders without restoring
• Ignoring character positions