Two Pointer Palindrome

TIP102 Unit 1 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Strings, Two-Pointer Technique

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• The function is_palindrome() should check if a given string reads the same backward as forward. Only lowercase alphabetic characters are considered.

HAPPY CASE
Input: "madam"
Expected Output: True

UNHAPPY CASE
Input: "madamweb"
Expected Output: False

EDGE CASE
Input: ""
Expected Output: True

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use two pointers to compare characters from both ends of the string and move towards the center.

1. Initialize two pointers: one at the beginning (left) and one at the end (right) of the string.
2. While the left pointer is less than the right pointer:
   a. If the characters at both pointers do not match, return False.
   b. Move the left pointer one step to the right and the right pointer one step to the left.
3. If all characters match, return True.

⚠️ Common Mistakes

• Forgetting to check both pointers before accessing the string.
• Not handling edge cases, such as empty strings.

I-mplement

Implement the code to solve the algorithm.

def is_palindrome(s):
    # Initialize two pointers
    left = 0
    right = len(s) - 1
    
    # Move the pointers towards each other
    while left < right:
        # If the characters at the pointers don't match, it's not a palindrome
        if s[left] != s[right]:
            return False
        # Move the pointers
        left += 1
        right -= 1
    
    # If all characters matched, it's a palindrome
    return True