Palindrome Detection in DSA Python - Time & Space Complexity

Time Complexity: Palindrome Detection

O(n)

Understanding Time Complexity

We want to know how the time to check if a word or phrase is a palindrome changes as the input gets longer.

How does the number of steps grow when the input size grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

This code checks if a string reads the same forwards and backwards by comparing characters from both ends moving towards the center.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing characters at positions from the start and end of the string.
• How many times: Up to half the length of the string (n/2) comparisons in the worst case.

How Execution Grows With Input

As the string gets longer, the number of character comparisons grows roughly half as fast.

Input Size (n)	Approx. Operations
10	5 comparisons
100	50 comparisons
1000	500 comparisons

Pattern observation: The number of steps grows linearly with input size, just half as many checks are needed.

Final Time Complexity

Time Complexity: O(n)

This means the time to check a palindrome grows in a straight line with the length of the string.

Common Mistake

[X] Wrong: "Checking a palindrome takes constant time because you just compare the first and last characters."

[OK] Correct: You must compare pairs of characters moving inward until the middle, so the time grows with the string length.

Interview Connect

Understanding how palindrome checking scales helps you explain your code clearly and shows you can analyze simple algorithms well.

Self-Check

"What if we used recursion instead of a loop? How would the time complexity change?"

Practice

1. What does it mean if a string is a palindrome?

easy

A. It contains only letters

B. It reads the same forwards and backwards

C. It has an even number of characters

D. It starts and ends with the same letter

Solution

1. Step 1: Understand palindrome definition

   A palindrome is a word or phrase that reads the same forwards and backwards.

2. Step 2: Compare options with definition

   Only It reads the same forwards and backwards matches this definition exactly.

3. Final Answer:

   It reads the same forwards and backwards -> Option B

4. Quick Check:

   Palindrome = Same forwards and backwards [OK]

Hint: Check if string equals its reverse [OK]

Common Mistakes:

• Thinking palindrome means only letters
• Assuming even length only
• Confusing start/end letters with palindrome

2. Which of the following Python code snippets correctly checks if a string s is a palindrome?

easy

A. s == reversed(s)

B. s == s[1:]

C. s == s.reverse()

D. s == s[::-1]

Solution

1. Step 1: Understand string reversal in Python

   The slice s[::-1] returns the reversed string.

2. Step 2: Check each option

   s == s[::-1] compares s to its reversed slice correctly. s == reversed(s) compares to an iterator, not a string. s == s.reverse() tries to use reverse() which is a list method and returns None. s == s[1:] compares to a substring missing the first character.

3. Final Answer:

   s == s[::-1] -> Option D

4. Quick Check:

   Use slicing to reverse string [OK]

Hint: Use s == s[::-1] to check palindrome [OK]

Common Mistakes:

• Using reversed() without join
• Calling reverse() on string
• Comparing to wrong substring

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

def is_palindrome(s):
    return s == s[::-1]

print(is_palindrome('level'))
print(is_palindrome('world'))

medium

A. True\nFalse

B. False\nTrue

C. True\nTrue

D. False\nFalse

Solution

1. Step 1: Check 'level' palindrome status

   'level' reversed is 'level', so is_palindrome('level') returns True.

2. Step 2: Check 'world' palindrome status

   'world' reversed is 'dlrow', which is different, so is_palindrome('world') returns False.

3. Final Answer:

   True\nFalse -> Option A

4. Quick Check:

   'level' palindrome True, 'world' not [OK]

Hint: Check string equals reversed string for each input [OK]

Common Mistakes:

• Assuming all strings are palindrome
• Mixing output order
• Confusing print output format

4. Find the error in this palindrome check function:

def check_palindrome(s):
    for i in range(len(s)):
        if s[i] != s[len(s)-i]:
            return False
    return True

medium

A. Function returns True too early

B. Loop should run only half the string length

C. Index out of range error in s[len(s)-i]

D. No error, function is correct

Solution

1. Step 1: Analyze index usage in loop

   Index len(s)-i is out of range because string indices go from 0 to len(s)-1.

2. Step 2: Identify correct index for reverse comparison

   It should be len(s)-i-1 to avoid index error.

3. Final Answer:

   Index out of range error in s[len(s)-i] -> Option C

4. Quick Check:

   Check index bounds carefully [OK]

Hint: Remember last index is len(s)-1 [OK]

Common Mistakes:

• Off-by-one error in indexing
• Looping full length instead of half
• Ignoring index errors

5. You want to check if a phrase is a palindrome ignoring spaces and capitalization. Which code snippet correctly implements this?

hard

A. s_clean = ''.join(c.lower() for c in s if c.isalpha())\nreturn s_clean == s_clean[::-1]

B. s_clean = s.replace(' ', '')\nreturn s_clean == s_clean[::-1]

C. s_clean = s.lower()\nreturn s_clean == s_clean[::-1]

D. s_clean = ''.join(c for c in s if c.isdigit())\nreturn s_clean == s_clean[::-1]

Solution

1. Step 1: Understand requirements

   We must ignore spaces and capitalization, and consider only letters.

2. Step 2: Analyze each option

   s_clean = ''.join(c.lower() for c in s if c.isalpha())\nreturn s_clean == s_clean[::-1] removes non-letters and lowercases all characters, then checks palindrome. s_clean = s.replace(' ', '')\nreturn s_clean == s_clean[::-1] only removes spaces but keeps punctuation and case. s_clean = s.lower()\nreturn s_clean == s_clean[::-1] keeps punctuation and spaces. s_clean = ''.join(c for c in s if c.isdigit())\nreturn s_clean == s_clean[::-1] keeps digits only, ignoring letters.

3. Final Answer:

   s_clean = ''.join(c.lower() for c in s if c.isalpha())\nreturn s_clean == s_clean[::-1] -> Option A

4. Quick Check:

   Filter letters and lowercase before palindrome check [OK]

Hint: Filter letters and lowercase before checking [OK]

Common Mistakes:

• Only removing spaces
• Ignoring punctuation
• Not lowercasing letters