15. Longest Palindrome in a String
Last updated
Was this helpful?
Last updated
Was this helpful?
The problem can be found at the following link:
To find the longest palindrome in a given string, I have used the following approach:
I implemented a straightforward approach using two pointers
to identify substrings and determine whether they are palindromic.
To optimize efficiency and avoid unnecessary checks, I started with larger substrings and gradually reduced their size.
I initialized an output string out
with the first character of the input string s
.
I also initialized a variable ms
to store the maximum length of the palindromic substring found so far, which is initially set to 1 (length of the first character).
I iterated over the string s
using two nested loops. The outer loop starts from the first character and goes up to the second-to-last character, while the inner loop starts from the last character and goes down to the character next to the current outer loop index.
For each combination of indices, I checked if the substring from i
to j
(inclusive) is a palindrome by comparing the characters at the corresponding indices using the ispalin
helper function.
If the current substring is a palindrome and its length is greater than ms
, I updated ms
with the new maximum length and stored the substring in out
using the substr
function.
Finally, I returned the out
string containing the longest palindromic substring.
Time Complexity: O(N^3)
, where N is the length of the input string. This is because we have nested loops that iterate over all possible substrings of s
, resulting in a cubic time complexity.
Auxiliary Space Complexity: O(1)
since we are not using any extra space that scales with the input.
For discussions, questions, or doubts related to this solution, please visit our . We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star
to the repository.