Longest Palindromic Substring
To find the longest palindromic substring in a given string, you can start from the middle of the palindrome and expand outwards to find the longest palindrome. Here’s a code snippet that demonstrates this approach:


Explanation:
 The
expandFromCenter
function returns the length of the palindrome that has its center betweenleft
andright
.  Iterate through the string and for each character, try to expand around that character to find a palindrome.
 Check for both oddlength palindromes (where the center is at one character) and evenlength palindromes (where the center is between two characters).
 Keep track of the longest palindrome found so far by updating
start
andend
.
This will return the longest palindromic substring in the given string s
.
Abstract Representation of the Problem
The abstract representation of this problem can be formulated as:
Problem Domain: Sequence Analysis
Objective: Given a sequence ( S ) composed of elements from a finite set ( \Lambda ), identify the longest contiguous subsequence ( T ) such that ( T ) is identical when read in reverse order.
Constraints:
 Length of ( S ) is bounded: ( 1 \leq S \leq 1000 ).
 ( \Lambda ) contains only digits and English letters.
Parameters:
 ( S )  The input sequence
 ( T )  The output subsequence
Operations:
 Iteration through sequence ( S ).
 Subsequence extraction.
 Validation of palindromic nature of the subsequence.
Functional Requirements:
 Return the longest such ( T ).
In this abstract representation, we’ve distilled the essence of the problem to its core elements: sequence, subsequence, constraints, and objectives. It generalizes the problem beyond strings and palindromes to a format that could apply to any sequence and its properties.
Cues
 Subsequence Extraction
 Validate Palindrome
Direction
Two Pointers
Identifying Problem Isomorphism
“Longest Palindromic Substring” can be approximately mapped to “Valid Palindrome”.
Reasoning:
Both problems deal with the concept of a palindrome, in slightly different contexts.
“Longest Palindromic Substring” is about finding the longest contiguous substring that is a palindrome.
“Valid Palindrome” checks if the given string can be read the same way from left to right and right to left ignoring cases, spaces, and punctuation.
The mapping is approximate because if a string is a valid palindrome, then the whole string is its longest palindromic substring. On the contrary, if a string has a longest palindromic substring, that does not guarantee that the whole string is a valid palindrome.
This mapping is approximate due to the difference in problem contexts and scopes.
“Longest Palindromic Substring” is a more complex problem because it requires not just to identify whether a palindrome exists, but also to identify the longest such substring. In contrast, the “Valid Palindrome” problem simply asks whether the given string (after ignoring certain characters) is a palindrome.
The problem is finding the longest palindromic substring in a given string. A palindrome is a string that reads the same forwards and backwards. The idea is to identify the longest such sequence within the input string.
The problem’s input is a string, and the output is also a string  the longest palindromic substring within the input string.
The base case for this problem is when the input string’s length is either 0 or 1. A string of length 0 obviously has no characters, and thus no palindrome, whereas a string of length 1 is inherently a palindrome.
For strings longer than 1 character, we have to consider three scenarios:
 The entire string is a palindrome
 The longest palindromic substring excludes the first character
 The longest palindromic substring excludes the last character
The solution provided uses a recursive approach to solve the problem. Recursion involves a function calling itself with different parameters until a base condition is met. This is the method employed in the Ruby function longest_palindrome?
as demonstrated in the provided code.
The palindrome?
function is a helper function that checks whether a given string is a palindrome by comparing it with its reverse.


The longest_palindrome?
function handles the main logic of the problem. It first checks the base case where if the string size is less than or equal to 1, it simply returns the string itself as the longest palindrome.


For larger strings, it attempts to find the longest palindrome by recursively calling itself with substrings of the original string. It does this by removing the first or the last character of the current string and checking for palindromes within the resulting substring.
However, as pointed out, this recursive solution will likely result in a Time Limit Exceeded (TLE) error for larger inputs. This is due to the high time complexity of the recursion, which has to compute the same subproblems multiple times. Each recursive call attempts to solve the problem for the whole substring, resulting in a lot of repeated work.
To optimize the solution, techniques such as memoization or dynamic programming (DP) can be used. Both of these techniques involve storing the results of expensive function calls and reusing them when the same inputs occur again, hence reducing the time complexity of the solution.
Problem Analysis
This is a string manipulation problem with a specific focus on finding palindromic patterns.
The fundamental concept revolves around identifying palindromes within a given string.
Core Problem: Find the longest contiguous substring that is palindromic.
Key Components:
 String
s
as input.  The constraint that
s.length
is between 1 and 1000.  Only digits and English letters are present in
s
.
Operations Needed:
 Iteration through the string.
 Palindrome identification.
 Substring extraction.
Problem Visualization
Imagine the string as a road, and you’re looking for the longest stretch where the sequence of characters looks the same when you move forward or backward along that stretch.
Simplification
Given a string s
, find the longest part of s
that reads the same forward and backward.
Constraints Exploitation
 The string length is capped at 1000, which gives some leeway in terms of computational complexity.
Insights
 Palindromes are mirror images around a central character or a pair of characters.
 Expanding outwards from each character can help find palindromes.
Examples for Edge Cases
Single Character:
 Input: “a”
 Output: “a”
 Explanation: Any single character is a palindrome.
All Characters Same:
 Input: “aaa”
 Output: “aaa”
 Explanation: The entire string is a palindrome.
No Palindromes:
 Input: “abc”
 Output: “a” or “b” or “c”
 Explanation: No palindromes longer than 1 character.
Stepwise Refinement
 Initialize variables to keep track of the longest palindrome found.
 Loop through each character in the string.
 For each character, expand outwards to find palindromes.
 Compare the length of any new palindrome found to the current longest, and update if necessary.
Repeatable Patterns
The pattern of expanding outwards from a character to find palindromes can be applied repeatedly for each character in the string.
Code


Time and Space Complexity
Time complexity: O(n^2)
Space complexity: O(1)
Here, n is the length of the string. We perform an O(n) operation (substring extraction) for each of the n characters in the worst case, making it O(n^2).
Similar LeetCode Problems
 Palindromic Substrings  Similar palindrome identification, but counting all palindromes.
 Valid Palindrome  Check if given string is a palindrome with extra constraints.
 Valid Palindrome II  Allows for one character to be removed.
 Longest Substring Without Repeating Characters  Similar string scanning for substring identification.
 Longest Repeating Character Replacement  Involves finding longest substring under certain conditions.
 Longest Common Prefix  Requires scanning through strings.
 Implement strStr()  Similar substring search.
 Reverse String  Involves characters in strings and manipulation.
 Reverse Vowels of a String  Involves scanning a string and reversing certain parts.
 First Unique Character in a String  Involves scanning through the string to find specific characters.
Each problem shares techniques like string scanning, substring identification, or palindrome identification, making them conceptually related.
Define the Interface
The input and output are:
Input: String
output: String
The base case is when the input string is either 0 or 1 in length. We have to consider three cases, the entire string can be a palindrome, if so that is the longest palindrome. If not, either the string that excludes the first character or the string that excludes the last character can be a palindrome. One of this can be the longest when we make recursive calls.
Recursive Solution
It is easy to make mistakes in discarding the last character because we are used to using n1 for the end of the string. To discard the last character we have to use n2 for reducing the input size to the recursive call.


This will work for small inputs but will result in Time Limit Exceeded error for large inputs.
Language Agnostic Coding Drills
Let’s break down the task of finding the Longest Palindromic Substring into smaller units of learning:
Understanding Variables and Data Types: This includes understanding the concept of variables and different data types like strings and integers.
 Drill: Create and manipulate string and integer variables.
String Manipulation and Indexing: In order to manipulate a string, you need to understand how to access its characters, slice it, reverse it, and check its length.
 Drill: Create a string, access characters via their indices, slice the string, reverse it, and check its length.
Loops: This task requires the use of nested loops to check all possible substrings of the string.
 Drill: Write a nested loop to print all substrings of a given string.
Conditional Statements: You need to use
if
statements to check whether a substring is a palindrome and whether it’s the longest one found so far. Drill: Write a code snippet that compares the lengths of two strings and performs operations based on the outcome of the comparison.
Functions: The task requires writing a function that finds the longest palindromic substring of a given string.
 Drill: Write a function that takes a string as input and returns its length.
Understanding Palindromes: A palindrome is a word, phrase, number, or other sequence of characters that reads the same backward or forward. Understanding this concept is key to this task.
 Drill: Write a function that checks whether a given string is a palindrome.
Finding Substrings: In this task, we need to find all substrings of a given string.
 Drill: Write a function that returns all substrings of a given string.
Understanding Longest Palindromic Substring Algorithm: This is about understanding the logic of the algorithm for finding the longest palindromic substring and how to implement it.
 Drill: Implement the Longest Palindromic Substring algorithm.
The increasing level of difficulty is determined by the complexity of the concepts and their application in understanding and implementing the Longest Palindromic Substring algorithm. The drills start with understanding basic concepts like variables, strings, and loops, then move to understanding and applying more complex concepts like conditional statements, functions, and palindromes, and finally to understanding and implementing the entire algorithm.
Solution for Coding Drills in Python
Understanding Variables and Data Types:
1 2 3
x = 10 y = "hello" print(x, y) # Output: 10 hello
String Manipulation and Indexing:
1 2 3 4 5
s = "palindrome" print(s[0]) # Output: p print(s[1:5]) # Output: alin print(s[::1]) # Output: emordnilap print(len(s)) # Output: 10
Loops:
1 2 3 4
s = "abc" for i in range(len(s)): for j in range(i+1, len(s)+1): print(s[i:j])
Conditional Statements:
1 2 3 4 5 6
s1 = "abc" s2 = "abcd" if len(s1) < len(s2): print("s1 is shorter than s2") # Output: s1 is shorter than s2 else: print("s1 is not shorter than s2")
Functions:
1 2 3 4
def length(s): return len(s) print(length("abc")) # Output: 3
Understanding Palindromes:
1 2 3 4 5
def is_palindrome(s): return s == s[::1] print(is_palindrome("radar")) # Output: True print(is_palindrome("python")) # Output: False
Finding Substrings:
1 2 3 4
def substrings(s): return [s[i:j] for i in range(len(s)) for j in range(i+1, len(s)+1)] print(substrings("abc")) # Output: ['a', 'ab', 'abc', 'b', 'bc', 'c']
Understanding Longest Palindromic Substring Algorithm:
1 2 3 4 5 6 7 8 9
def longest_palindromic_substring(s): res = "" for i in range(len(s)): for j in range(i+1, len(s)+1): if s[i:j] == s[i:j][::1] and len(s[i:j]) > len(res): res = s[i:j] return res print(longest_palindromic_substring("babad")) # Output: "bab"
Problem Solving
The problem statement for the “Longest Palindromic Substring” problem is:
"Given a string s, return the longest palindromic substring in s."
Let’s break down the steps for analyzing this problem and developing a solution:
Understand the problem: The first step in any problemsolving is to understand the problem thoroughly. Here, we’re asked to find the longest substring in a given string
s
that is a palindrome. A palindrome is a word, phrase, number, or other sequences of characters that reads the same forward and backward, ignoring spaces, punctuation, and capitalization.Identify the problem type: Next, identify the type of problem you’re dealing with. Is it a dynamic programming problem? Is it a problem that requires greedy algorithms? Is it a search problem? A sorting problem? In this case, it’s a string manipulation problem, which could be solved with dynamic programming, expanding around the center or Manacher’s algorithm. Here we’ll use expanding around the center for simplicity.
Define the approach: After identifying the problem type, define your approach. In this case, the approach is to iterate over the string and for each character, expand around it to find the largest palindrome centered at that character. Keep track of the longest palindrome seen so far.
Pseudocode: Write pseudocode for the solution. This can help you understand the solution’s flow and make actual code writing easier.
 Loop over the string
 For each character, find the longest palindrome centered at that character
 Update the longest palindrome if the current palindrome is longer
 Continue until all characters have been checked
 Return the longest palindrome
Translate into code: Now, you can translate the pseudocode into actual code. Check the code for syntax and logic errors.
Test the code: Finally, test your code with different test cases, including edge cases, to make sure it’s working as expected.
This is the general stepbystep process for problem analysis and solution development in programming problems. Keep in mind that practice is key. The more problems you solve, the better you’ll get at this process.
Q&A
Let’s discuss a method for finding the longest palindromic substring within a given string ( s ).
Overview
For each character ( s[i] ), the algorithm tries to find the longest palindromic substring that has ( s[i] ) as its center or part of its center (in case the palindrome has even length).
StepbyStep Explanation
Identify Repeating Characters:
 For each ( s[i] ), find the index ( \text{right} ) of the first character to its right that is not equal to ( s[i] ).
 This gives us a substring ( s[i, \text{right}  1] ) where all characters are the same. For example, if ( s[i] = ‘a’ ), and ( \text{right} = 4 ), then ( s[1,3] = “aaa” ).
Initial Palindrome Center:
 Set ( \text{left} = i  1 ) and ( \text{right} ) as it was found in the previous step.
 You have ( s[\text{left} + 1, \text{right}  1] ) as a base palindrome centered around ( s[i] ).
Extend the Palindrome:
 While ( s[\text{left}] = s[\text{right}] ), extend the palindrome outwards.
 You’re essentially checking the characters symmetrically around ( s[i] ) to see if they are the same. If they are, you extend ( \text{left} ) and ( \text{right} ) by one position outward, i.e., ( \text{left} = 1 ) and ( \text{right} += 1 ).
Update Longest Palindrome:
 After you can no longer extend ( \text{left} ) and ( \text{right} ), you’ve found a palindromic substring. If this new palindromic substring is longer than the longest one you’ve found so far, update your tracking variables to keep this new one.
The key insight here is that by beginning with a palindrome center (which may be a single character or a block of repeating characters) and then symmetrically expanding outward, you can efficiently discover palindromic substrings. This approach leverages the very definition of a palindrome: a sequence that reads the same forward and backward.
A table can be used to visualize these steps. Let’s consider an example string ( s = \text{“abba”} ) and we’re examining the character ( s[1] = \text{“b”} ).
Step  Description  ( s )  ( i )  ( \text{left} )  ( \text{right} )  Palindrome  Action 

Identify Repeating Characters  Find the index ( \text{right} ) where the character changes  “abba”  1    2  “bb”  ( s[1, \text{right}1] = \text{“bb”} ) 
Initial Palindrome Center  Set ( \text{left} = i  1 )  “abba”  1  0  2  “bb”  ( \text{left} = i  1 ) 
Extend the Palindrome (Step 1)  Check if ( s[\text{left}] = s[\text{right}] ) and extend  “abba”  1  0  2  “abba”  ( s[0] = s[2] ) ( \Rightarrow ) extend 
Extend the Palindrome (Step 2)  No more extensions possible (outside the string limits)  “abba”  1  1  3  “abba”  Cannot extend anymore 
Update Longest Palindrome  Check if this palindrome is longer than the previously longest one  “abba”  1  1  3  “abba”  Update longest palindrome if this one is longer 
This table shows the four main steps with ( s[1] = \text{“b”} ) as the focus in the string ( s = \text{“abba”} ). The same process would be repeated for every character in the string to ensure we find the longest palindromic substring.
Why does the index i start from 1?
The index ( i ) starts from 1 in this example to demonstrate how to find palindromes around a “center” character. If ( i ) started at 0, there wouldn’t be any characters before it to extend the palindrome to the left side.
However, in a real implementation, you would actually start with ( i = 0 ) and consider that you can’t extend the palindrome to the left when ( i = 0 ), or to the right when ( i = n1 ) where ( n ) is the length of the string. Starting from ( i = 1 ) in the example was purely for illustration purposes to show how extending works on both sides of a character.
Can you explain the steps without any implementation details to make it easy to understand?
Imagine you’re looking at a string of characters, and you want to find the longest sequence that reads the same forwards and backwards, known as a palindrome.
 You start by picking a character in the string.
 You look at the characters immediately to the left and right of your chosen one.
 You expand outwards from this point, checking if the characters on both sides are the same.
 If they are, you keep moving outward and continue to check.
 You stop when the characters are not the same or you reach the end of the string.
 The sequence you’ve checked is a palindrome.
 You repeat these steps for every character in the string.
 The longest sequence you find this way is the longest palindromic substring.
In this way, you are exploring around each character to find palindromes.
Why not consider the entire string first, then the entire string without the last character and then the entire string without the first character?
Considering the entire string first and then removing characters one by one from the ends is a valid approach, but it is not efficient. For a string of length ( n ), there could be ( O(n^2) ) substrings to consider. For each of those substrings, you would need to check if it is a palindrome, which takes ( O(n) ) time. Therefore, the total time complexity would be ( O(n^3) ).
On the other hand, if you start from each character and expand outwards to find palindromes, you only need ( O(n) ) time to check around each character. Since there are ( n ) characters, the total time complexity would be ( O(n^2) ), which is more efficient than ( O(n^3) ).
The “expand outwards” method efficiently narrows down the regions of the string where a palindrome could exist, saving you from having to check many substrings that have no chance of being palindromes.
Can you show by visual to illustrate the cubic vs quadratic difference when using the string?
Let’s take a string ( s = “racecar” ) as an example. It has 7 characters.
Cubic Time Complexity (( O(n^3) ))
In this approach, you would have to consider all possible substrings and then check if they are palindromic.
Here’s the table for all possible substrings of the string “racecar”, with a “Step Number” column added for better tracking.
Step Number  Start Index  End Index  Substring 

1  0  0  r 
2  1  1  a 
3  2  2  c 
4  3  3  e 
5  4  4  c 
6  5  5  a 
7  6  6  r 
8  0  1  ra 
9  1  2  ac 
10  2  3  ce 
11  3  4  ec 
12  4  5  ca 
13  5  6  ar 
14  0  2  rac 
15  1  3  ace 
16  2  4  cec 
17  3  5  eca 
18  4  6  car 
19  0  3  race 
20  1  4  acec 
21  2  5  ceca 
22  3  6  ecar 
23  0  4  racec 
24  1  5  aceca 
25  2  6  cecar 
26  0  5  raceca 
27  1  6  acecar 
28  0  6  racecar 
Each entry shows a unique substring, starting from the shortest to the longest. The table keeps track of each step to make it easier to understand the progression.
For each of these substrings, you check if they are palindromic (( O(n) ) time). Since there are ( O(n^2) ) substrings, the total time is ( O(n^3) ).
Quadratic Time Complexity (( O(n^2) ))
In this approach, you start at each character and expand outwards to look for palindromes.
 Start at ‘r’: Only one palindrome > “r”
 Start at ‘a’: Only one palindrome > “a”
 Start at ‘c’: Palindromes > “c”, “aceca”
 …
 Start at ‘r’: Only one palindrome > “r”
Each “expansion” takes ( O(n) ) time, but you do it ( n ) times, making the total time ( O(n^2) ).
Visualization
Cubic Time Complexity: Imagine a cube where each unit inside has to be inspected. That’s ( n \times n \times n ) units.
[ \boxed{\boxed{\boxed{—}}} ] [ \boxed{\boxed{\boxed{—}}} ] [ \boxed{\boxed{\boxed{—}}} ]
Quadratic Time Complexity: Imagine a square where each unit inside the square has to be inspected. That’s ( n \times n ) units.
[ \boxed{—} ] [ \boxed{—} ] [ \boxed{—} ]
The quadratic method has fewer “units” to inspect, making it more efficient.
For racecar show all possible substrings in a table.
Here’s a table showing all possible substrings for the string “racecar”.
Step Number  Central Point  Start Index  End Index  Checked Substring 

1  r  0  0  r 
2  a  1  1  a 
3  c  2  2  c 
4  e  3  3  e 
5  c  4  4  c 
6  a  5  5  a 
7  r  6  6  r 
8  ra/ar  0  1  ra 
9  ac/ca  1  2  ac 
10  ce/ec  2  3  ce 
11  ec/ce  3  4  ec 
12  ca/ac  4  5  ca 
13  ar/ra  5  6  ar 
14  rac/car  0  2  rac 
15  ace/cea  1  3  ace 
16  cec/ec  2  4  cec 
17  eca/ace  3  5  eca 
18  car/rac  4  6  car 
19  race/cear  0  3  race 
20  acec/ceca  1  4  acec 
21  ceca/acec  2  5  ceca 
22  ecar/race  3  6  ecar 
23  racec/ecar  0  4  racec 
24  aceca/ceca  1  5  aceca 
25  cecar/racec  2  6  cecar 
26  raceca/ecar  0  5  raceca 
27  acecar/cecra  1  6  acecar 
28  racecar  0  6  racecar 
The table follows a 0based index system, and the ‘Start Index’ and ‘End Index’ indicate the indices of the first and last characters of each substring, respectively.
Both have 28 steps so how is one more efficient than the other?
Good observation. The number of steps in that table represents the number of substrings, which would be the same for both cubic and quadratic algorithms. However, the efficiency comes into play when you consider how each algorithm checks for palindromes.
In a cubic algorithm, for each substring, you’d typically use a nested loop to compare characters to check if it’s a palindrome. That’s a third loop, making the algorithm cubic (O(n^3)).
In a quadratic algorithm, you’d generate a palindrome substring centered at each character in (O(1)) time, and then expand outwards in (O(n)) time, making it quadratic (O(n^2)).
The efficiency gain is not in generating the substrings but in how we check for palindromes. The quadratic algorithm uses the characters in the given string more effectively to determine palindromes, eliminating the need for a third loop.
The quadratic algorithm checks for palindrome as part of processing the string on the fly?
Yes, exactly. The quadratic algorithm often uses a “center and expand” technique. It treats each character in the string as the center of a possible palindrome and then expands outwards, checking for palindromes as it goes. This allows it to identify palindromes in (O(1)) time for each center, which leads to an overall (O(n^2)) time complexity. There is no need for an additional loop to check each substring for palindromic properties, which is why it’s more efficient than the cubic approach.
What is the loop invariant in the quadratic algorithm?
In the context of the quadratic algorithm for finding palindromes, the loop invariant could be that “for each center considered up to (i), the longest palindromic substring among those centers has been correctly identified.”
This invariant holds true at the beginning of the loop, where (i = 0) and no centers have been considered, so the longest palindromic substring is an empty string. Then, as each new center (i) is considered, the algorithm correctly identifies the longest palindromic substring around that center and updates the longest palindrome found so far if necessary. Finally, the invariant ensures that at the end of the loop, the longest palindromic substring in the entire string has been correctly identified.
Understanding this loop invariant helps in ensuring that the algorithm is both correct and efficient.
Not all substrings considered will be a palindrome in the quadratic algorithm, we keep finding the palindromes and keep track of the longest one we have seen so far.
Correct. In the quadratic algorithm for finding the longest palindromic substring, not every substring is a palindrome. The algorithm identifies potential centers of palindromes and expands outwards from those centers, checking for palindromic conditions. If a palindrome is found, its length is compared to the longest one found so far, and if it’s longer, it replaces it. Thus, the algorithm keeps track of the longest palindromic substring seen up to each point. This way, you don’t have to check every single substring; you just expand from potential centers, saving computational time.
One of the top 100 questions asked by Amazon. Recursive solution to solving longest palindromic substring.
Longest Palindromic Substring
This question is Amazon’s top 100 questions asked during the interview. Given a string s, find the longest palindromic substring in s. Example:
Input: 'babad'
Output 'bab' or 'aba'
I had to make corrections to the code in my videos on how to solve this problem. The fixes are:
 To exclude the last character, you have to use n2 because the s[0] == s[n1] checks the first and last character.
 Going from first character to and less than the last character requires s[0..n2]. It’s not s[0..n1].


Next step is to make this solution optimal by using dynamic programming.
excerpt: Recursion, Recursion with Memoization and DP solutions tags: palindrome memoization
The input and output are:
Input: String
output: String
The base case is when the input string is either 0 or 1 in length. We have to consider three cases, the entire string can be a palindrome, if so that is the longest palindrome. If not, either the string that excludes the first character or the string that excludes the last character can be a palindrome. One of this can be the longest when we make recursive calls.
Recursive Solution
It is easy to make mistakes in discarding the last character because we are used to using n1 for the end of the string. To discard the last character we have to use n2 for reducing the input size to the recursive call.


This will work for small inputs but will result in Time Limit Exceeded error for large inputs.