Computer Science
Updated 23 days ago | GitHub

The Longest Mirror

TIP103 Unit 12 Session 1 (Click for link to problem statements)

The Longest Mirror

Given a string s, find the longest contiguous stretch that reads the same forwards and backwards.

Return that longest palindromic substring; if more than one has the maximum length, any of them is acceptable.

def longest_palindrome(s):
    pass

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 25-30 mins
  • 🛠️ Topics: Strings, Palindromes, Two Pointers, Expand Around Center

1: 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?

  • Q: What counts as a “mirror” here?

    • A: A contiguous substring that is a palindrome — reversing it produces the same string, e.g. "bab" or "bb". It must be consecutive characters (a substring), not a subsequence.

  • Q: What should we return if several palindromic substrings tie for the maximum length?

    • A: Any one of them is acceptable. For "babad", both "bab" and "aba" are valid answers.

  • Q: Do we need to consider even-length palindromes as well as odd-length ones?

    • A: Yes. "bb" in "cbbd" is an even-length palindrome, so both kinds of centers must be checked.
HAPPY CASE
Input: s = "babad"
Output: "bab"
Explanation: "bab" is a palindrome of length 3, the longest in the string. ("aba" would also be accepted.)

Input: s = "cbbd"
Output: "bb"
Explanation: The longest mirror here has even length; "bb" reads the same in both directions.

EDGE CASE
Input: s = "abc"
Output: "a"
Explanation: No two adjacent characters match, so the longest palindrome is any single character.

Input: s = "racecar"
Output: "racecar"
Explanation: The entire string is a palindrome, so the whole string is returned.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Palindrome / Substring Problems, we can consider the following approaches:

  • Expand Around Center (Two Pointers): Every palindrome is symmetric about a center. Try each of the 2N - 1 possible centers (each character for odd lengths, each gap between adjacent characters for even lengths) and grow two pointers outward while the characters mirror each other.
  • Dynamic Programming: A table dp[i][j] can record whether s[i..j] is a palindrome, but it costs O(N^2) space, whereas expanding around centers achieves the same O(N^2) time in constant space.
  • Brute Force: Checking every substring for being a palindrome is O(N^3) — too slow for anything but tiny inputs.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Treat each index as the potential center of a palindrome. From every center, use two pointers to expand outward while the left and right characters match. Track the bounds of the longest palindrome seen so far, checking both an odd-length center (a single character) and an even-length center (a pair of adjacent characters) at each position.

1) If the string is empty, return "".
2) Track `start` and `end`, the bounds of the best palindrome found so far.
3) Define a helper expand(left, right):
   a) While left and right are in bounds and s[left] == s[right], move left one step left and right one step right.
   b) The loop overshoots by one on each side, so return (left + 1, right - 1).
4) For each index i in the string:
   a) Expand around the odd center (i, i); if the result is longer, update start/end.
   b) Expand around the even center (i, i+1); if the result is longer, update start/end.
5) Return the slice s[start..end].

⚠️ Common Mistakes

  • Only checking odd-length centers (i, i) and missing even-length palindromes like "bb" in "cbbd".
  • Forgetting that the expansion loop stops one step past the palindrome on each side, and returning the wrong bounds.
  • Building a new substring on every expansion instead of tracking indices, which does extra copying work.
  • Returning the length of the palindrome instead of the palindrome itself.

4: I-mplement

Implement the code to solve the algorithm.

def longest_palindrome(s):
    if not s:
        return ""

    start, end = 0, 0  # Bounds of the best palindrome found so far

    def expand(left, right):
        # Grow outward while the characters mirror each other
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        # The loop overshoots by one on each side
        return left + 1, right - 1

    for i in range(len(s)):
        # Odd-length palindrome centered at index i
        l1, r1 = expand(i, i)
        if r1 - l1 > end - start:
            start, end = l1, r1
        # Even-length palindrome centered between i and i+1
        l2, r2 = expand(i, i + 1)
        if r2 - l2 > end - start:
            start, end = l2, r2

    return s[start:end + 1]

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code’s variables along the way.

  • Input: s = “babad”

    • Center i = 0 ('b'): odd expansion yields only "b"; best bounds stay (0, 0).
    • Center i = 1 ('a'): odd expansion matches s[0] == s[2] ('b' == 'b'), then stops at the left boundary, yielding "bab"; best bounds become (0, 2).
    • Center i = 2 ('b'): odd expansion yields "aba", also length 3, so the bounds are not updated.
    • Remaining centers find nothing longer, and no even center ever matches.
    • Output: “bab”

  • Input: s = “cbbd”

    • Odd centers each yield only single characters.
    • Even center i = 1 (s[1] and s[2]): 'b' == 'b', expansion stops when 'c' != 'd', yielding "bb"; best bounds become (1, 2).
    • Output: “bb”

  • Input: s = “racecar”

    • Center i = 3 ('e'): expansion matches all the way out to both ends of the string.
    • Output: “racecar” (the entire string is a palindrome).

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the length of the string s.

  • Time Complexity: O(N^2) because there are 2N - 1 centers and each expansion can extend up to O(N) steps outward.
  • Space Complexity: O(1) extra space, since we only track indices; the final slice for the answer is O(N), the size of the output itself.