Problem Statement

Given a string s, return the longest palindromic substring in s.

A string is called palindromic if it reads same from forward as backward.

A substring is a contiguous sequence of characters in the string.

Examples

• Example 1:

  • Input: s = "racecar"
  • Expected Output: "racecar"
  • Justification: The entire string is a palindrome and is the longest substring.

• Example 2:

  • Input: s = "abccd"
  • Expected Output: "cc"
  • Justification: The longest palindromic substring is "cc" in the string abccd.

• Example 3:

  • Input: s = "xyzzy"
  • Expected Output: "yzzy"
  • Justification: The substring "yzzy" is the longest palindromic substring.

Solution

To solve this problem, the Expand Around Center technique is an effective approach. The idea is to consider each character in the string as the center of a potential palindrome and expand in both directions to find the length of the palindrome. This technique is efficient because it utilizes the symmetry of palindromes and checks for both odd and even length palindromes by expanding around a center point or a center gap. This approach is most effective because it directly narrows down the search to potential palindromic centers, reducing unnecessary comparisons, and it can handle palindromes of both odd and even lengths without requiring additional data structures.

The key to this method is to iterate over the string, treating each character and each gap between characters as potential centers of palindromes. For each center, we expand outwards, comparing characters until they no longer match. We record the length of each palindrome found and update the maximum palindrome length accordingly. This process is repeated until all potential centers have been examined. The simplicity and directness of expanding around centers make this method both intuitive and efficient for finding the longest palindromic substring.

Step-by-Step Algorithm

1. Check for Empty String: If the input string s is empty or null, return an empty string since there's no palindrome to find.

2. Initialize Start and End Indices: Start and end indices (start and end) are initialized to track the boundaries of the longest palindromic substring found so far. Initially, both are set to 0.

3. Iterate Through the String: Loop through each character in the string with index i. For each character, two types of palindrome checks are performed: one assuming the current character as the center of an odd-length palindrome and another assuming the current character and the next character as the center for an even-length palindrome.

4. Expand Around Centers: For each character at index i:

   • Call expandAroundCenter(s, i, i) to check for the longest odd-length palindrome centered at i.
   • Call expandAroundCenter(s, i, i + 1) to check for the longest even-length palindrome centered between i and i + 1.
   • Compare the lengths of these two palindromes and keep the length of the longer one.

5. Update Longest Palindrome Boundaries: If the palindrome found is longer than the current longest palindrome (end - start), update the start and end indices to the new boundaries of this palindrome.

6. Return the Longest Palindromic Substring: Use the start and end indices to extract the longest palindromic substring from s and return it.

Helper Function expandAroundCenter()

1. Initialize Pointers: This function receives the string s and two indices, left and right, which represent the center of the palindrome to be expanded.

2. Expand the Palindrome: While left and right are within the bounds of the string and the characters at these indices are equal, decrement left and increment right. This expansion continues as long as the substring is a palindrome.

3. Return Length: Once the expansion stops, return the length of the palindrome found by calculating right - left - 1. This subtraction accounts for the last increment and decrement that occurred when the while loop condition failed.

Algorithm Walkthrough

Let's consider the input: s = "xyzzy".

1. Initialize Variables: start = 0, end = 0. These variables will keep track of the start and end indices of the longest palindromic substring found so far.

2. Loop Through String Characters:

   • Iteration 1: i = 0
     • Inner Loop (Odd Length Palindrome):
       • len1 = expandAroundCenter("xyzzy", 0, 0). Since s.charAt(0) == s.charAt(0), the loop expands.
       • Once expanded, left = -1 and right = 1, so len1 = right - left - 1 = 1.
     • Inner Loop (Even Length Palindrome):
       • len2 = expandAroundCenter("xyzzy", 0, 1). Since s.charAt(0) != s.charAt(1), the loop breaks. len2 = 0.
     • Comparison:
       • len = max(1, 0) = 1. Since len > end - start, update start = 0, end = 0.
   • Iteration 2: i = 1
     • Inner Loop (Odd Length Palindrome):
       • len1 = expandAroundCenter("xyzzy", 1, 1). Since s.charAt(1) == s.charAt(1), the loop expands.
       • Once expanded, left = 0 and right = 2, so len1 = right - left - 1 = 1.
     • Inner Loop (Even Length Palindrome):
       • len2 = expandAroundCenter("xyzzy", 1, 2). Since s.charAt(1) != s.charAt(2), the loop breaks. len2 = 0.
     • Comparison:
       • len = max(1, 0) = 1. Since len > end - start, no update.
   • Iteration 3: i = 2
     • Inner Loop (Odd Length Palindrome):
       • len1 = expandAroundCenter("xyzzy", 2, 2). Since s.charAt(2) == s.charAt(2), the loop expands.
       • Once expanded, left = 1 and right = 3, so len1 = right - left - 1 = 1.
     • Inner Loop (Even Length Palindrome):
       • len2 = expandAroundCenter("xyzzy", 2, 3). Since s.charAt(2) == s.charAt(3), the loop expands.
       • Since s.charAt(1) == s.charAt(4), the loop expands
       • Once expanded, left = 0 and right = 5, so len2 = right - left - 1 = 4.
     • Comparison:
       • len = max(1, 4) = 4. Since len > end - start, update start = 1, end = 4.
   • Iteration 4: i = 3
     • Inner Loop (Odd Length Palindrome):
       • len1 = expandAroundCenter("xyzzy", 3, 3). Since s.charAt(3) == s.charAt(3), the loop expands.
       • Once expanded, left = 2 and right = 4, so len1 = right - left - 1 = 1.
     • Inner Loop (Even Length Palindrome):
       • len2 = expandAroundCenter("xyzzy", 3, 4). Since s.charAt(3) != s.charAt(4), the loop doesn't expand.
     • Comparison:
       • len = max(1, 0) = 1. Since len < end - start, no update.
   • Iteration 5: i = 4
     • Inner Loop (Odd Length Palindrome):
       • len1 = expandAroundCenter("xyzzy", 4, 4). Since s.charAt(4) == s.charAt(4), the loop expands.
       • Once expanded, left = 3 and right = 5, so len1 = right - left - 1 = 1.
     • Inner Loop (Even Length Palindrome):
       • len2 = expandAroundCenter("xyzzy", 4, 5). Since the index is out of bounds, the loop doesn't expand.
     • Comparison:
       • len = max(1, 0) = 1. Since len < end - start, no update.

3. Return Result: The longest palindromic substring is "yzzy".

Code