0% completed
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.
- Input: s =
-
Example 2:
- Input: s =
"abccd"
- Expected Output:
"cc"
- Justification: The longest palindromic substring is
"cc"
in the stringabccd
.
- Input: s =
-
Example 3:
- Input: s =
"xyzzy"
- Expected Output:
"yzzy"
- Justification: The substring
"yzzy"
is the longest palindromic substring.
- Input: s =
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
-
Check for Empty String: If the input string
s
is empty or null, return an empty string since there's no palindrome to find. -
Initialize Start and End Indices: Start and end indices (
start
andend
) are initialized to track the boundaries of the longest palindromic substring found so far. Initially, both are set to 0. -
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. -
Expand Around Centers: For each character at index
i
:- Call
expandAroundCenter(s, i, i)
to check for the longest odd-length palindrome centered ati
. - Call
expandAroundCenter(s, i, i + 1)
to check for the longest even-length palindrome centered betweeni
andi + 1
. - Compare the lengths of these two palindromes and keep the length of the longer one.
- Call
-
Update Longest Palindrome Boundaries: If the palindrome found is longer than the current longest palindrome (
end - start
), update thestart
andend
indices to the new boundaries of this palindrome. -
Return the Longest Palindromic Substring: Use the
start
andend
indices to extract the longest palindromic substring froms
and return it.
Helper Function expandAroundCenter()
-
Initialize Pointers: This function receives the string
s
and two indices,left
andright
, which represent the center of the palindrome to be expanded. -
Expand the Palindrome: While
left
andright
are within the bounds of the string and the characters at these indices are equal, decrementleft
and incrementright
. This expansion continues as long as the substring is a palindrome. -
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"
.
-
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. -
Loop Through String Characters:
- Iteration 1:
i = 0
- Inner Loop (Odd Length Palindrome):
len1 = expandAroundCenter("xyzzy", 0, 0)
. Sinces.charAt(0) == s.charAt(0)
, the loop expands.- Once expanded,
left = -1
andright = 1
, solen1 = right - left - 1 = 1
.
- Inner Loop (Even Length Palindrome):
len2 = expandAroundCenter("xyzzy", 0, 1)
. Sinces.charAt(0) != s.charAt(1)
, the loop breaks.len2 = 0
.
- Comparison:
len = max(1, 0) = 1
. Sincelen > end - start
, updatestart = 0
,end = 0
.
- Inner Loop (Odd Length Palindrome):
- Iteration 2:
i = 1
- Inner Loop (Odd Length Palindrome):
len1 = expandAroundCenter("xyzzy", 1, 1)
. Sinces.charAt(1) == s.charAt(1)
, the loop expands.- Once expanded,
left = 0
andright = 2
, solen1 = right - left - 1 = 1
.
- Inner Loop (Even Length Palindrome):
len2 = expandAroundCenter("xyzzy", 1, 2)
. Sinces.charAt(1) != s.charAt(2)
, the loop breaks.len2 = 0
.
- Comparison:
len = max(1, 0) = 1
. Sincelen > end - start
, no update.
- Inner Loop (Odd Length Palindrome):
- Iteration 3:
i = 2
- Inner Loop (Odd Length Palindrome):
len1 = expandAroundCenter("xyzzy", 2, 2)
. Sinces.charAt(2) == s.charAt(2)
, the loop expands.- Once expanded,
left = 1
andright = 3
, solen1 = right - left - 1 = 1
.
- Inner Loop (Even Length Palindrome):
len2 = expandAroundCenter("xyzzy", 2, 3)
. Sinces.charAt(2) == s.charAt(3)
, the loop expands.- Since
s.charAt(1) == s.charAt(4)
, the loop expands - Once expanded,
left = 0
andright = 5
, solen2 = right - left - 1 = 4
.
- Comparison:
len = max(1, 4) = 4
. Sincelen > end - start
, updatestart = 1
,end = 4
.
- Inner Loop (Odd Length Palindrome):
- Iteration 4:
i = 3
- Inner Loop (Odd Length Palindrome):
len1 = expandAroundCenter("xyzzy", 3, 3)
. Sinces.charAt(3) == s.charAt(3)
, the loop expands.- Once expanded,
left = 2
andright = 4
, solen1 = right - left - 1 = 1
.
- Inner Loop (Even Length Palindrome):
len2 = expandAroundCenter("xyzzy", 3, 4)
. Sinces.charAt(3) != s.charAt(4)
, the loop doesn't expand.
- Comparison:
len = max(1, 0) = 1
. Sincelen < end - start
, no update.
- Inner Loop (Odd Length Palindrome):
- Iteration 5:
i = 4
- Inner Loop (Odd Length Palindrome):
len1 = expandAroundCenter("xyzzy", 4, 4)
. Sinces.charAt(4) == s.charAt(4)
, the loop expands.- Once expanded,
left = 3
andright = 5
, solen1 = 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
. Sincelen < end - start
, no update.
- Inner Loop (Odd Length Palindrome):
- Iteration 1:
-
Return Result: The longest palindromic substring is
"yzzy"
.
Code
Complexity Analysis
Time Complexity
- O(n^2): The main factor contributing to the time complexity is the need to expand around each character (and each pair of characters for even-length palindromes) to check for palindromic substrings. For each of the
n
characters, the expansion in the worst case can go up ton
characters (if the entire string from that point is a palindrome). Therefore, the time complexity is quadratic, O(n^2).
Space Complexity
- O(1): The space complexity is constant because the space used does not scale with the input size.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible