grid47 Exploring patterns and algorithms
Nov 6, 2024
5 min read
Solution to LeetCode 5: Longest Palindromic Substring Problem
Given a string, find and return the longest palindromic substring in it. A palindrome is a word that reads the same forward and backward. The substring must be contiguous within the original string.
Problem
Approach
Steps
Complexity
Input: The input is a string 's'.
Example: s = "racecar"
Constraints:
• 1 <= s.length <= 1000
• s consists of only digits and English letters.
Output: The output should be the longest palindromic substring from the input string.
Example: "aceca"
Constraints:
• The returned substring must be the longest palindromic substring found.
Goal: To efficiently find the longest substring that is a palindrome.
Steps:
• Iterate over each character in the string as the center of the potential palindrome.
• Expand outwards from the center for both odd and even length palindromes.
• Keep track of the longest palindrome found during this process.
Goal: The function must handle strings of varying lengths up to 1000 characters.
Steps:
• The string must contain only printable characters, including letters and digits.
Assumptions:
• The input string is valid and contains at least one character.
• The palindrome may be a single character if no longer palindromes are found.
• Input: s = "bananas"
• Explanation: The longest palindromic substring is "anana" with a length of 5.
• Input: s = "civic"
• Explanation: The entire string "civic" is a palindrome, and it is the longest one.
• Input: s = "hello"
• Explanation: The longest palindromic substring is "e" with a length of 1.
Approach: A center-expansion approach can be used to identify palindromes around each character in the string.
Observations:
• We can treat each character as a potential center for a palindrome.
• Palindromes can either have odd or even lengths, so we must check both possibilities.
• Instead of checking all possible substrings, we can expand from the center, which reduces the number of comparisons needed.
Steps:
• For each character in the string, treat it as the center of a potential palindrome.
• Expand outwards while checking for palindromes in both directions (odd and even length).
• Track the longest palindrome found during the expansion process.
Empty Inputs:
• If the string is empty, return an empty string.
Large Inputs:
• The solution should efficiently handle strings up to the length of 1000.
Special Values:
• Strings with no palindrome longer than 1 character should return a single character.
• Strings that are themselves palindromes should return the entire string.
Constraints:
• The string only contains printable characters.
int lo, len;
string longestPalindrome(string s) {
len =0;
for(int i =0; i < s.size(); i++) {
pal(s, i, i);
pal(s, i, i +1);
}
return s.substr(lo, len);
}
voidpal(string &s, int i, int j) {
while(i >=0&& j <= s.size() && s[i] == s[j]) {
i--;
j++;
}
if(len < j - i -1) {
lo = i +1;
len = j - i -1;
}
}
1 : Variable Initialization
int lo, len;
Declare and initialize variables `lo` and `len` to store the starting index and length of the longest palindrome found so far.
2 : Function Declaration
string longestPalindrome(string s) {
Declare the `longestPalindrome` function, which takes a string `s` as input and returns the longest palindromic substring.
3 : Initialization
len =0;
Initialize `len` to 0, as we haven't found a palindrome yet.
4 : Loop Iteration
for(int i =0; i < s.size(); i++) {
Iterate over each character in the string `s`.
5 : Function Call
pal(s, i, i);
Call the `pal` function to check for odd-length palindromes centered at index `i`.
6 : Function Call
pal(s, i, i +1);
Call the `pal` function to check for even-length palindromes centered between indices `i` and `i+1`.
7 : Return Value
return s.substr(lo, len);
Return the longest palindrome substring found.
8 : Function Declaration
voidpal(string &s, int i, int j) {
Declare the `pal` function to check for palindromes around a given center.
9 : Loop Iteration
while(i >=0&& j <= s.size() && s[i] == s[j]) {
Expand the palindrome as long as the characters at indices `i` and `j` match.
10 : Index Update
i--;
Decrement `i` to move to the previous character.
11 : Index Update
j++;
Increment `j` to move to the next character.
12 : Conditional Check
if(len < j - i -1) {
Check if the current palindrome is longer than the previously found longest palindrome.
13 : Variable Assignment
lo = i +1;
Update `lo` to store the starting index of the new longest palindrome.
14 : Variable Assignment
len = j - i -1;
Update `len` to store the length of the new longest palindrome.
Best Case: O(n^2)
Average Case: O(n^2)
Worst Case: O(n^2)
Description: In the worst case, we may need to expand around each character in the string, which results in a time complexity of O(n^2).
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) because we only need a constant amount of extra space for variables like the longest palindrome's start position and length.
