Last active
March 5, 2024 20:46
-
-
Save mlivingston40/328c761b94243998495d3a1886e6eb8a to your computer and use it in GitHub Desktop.
Given a string s, return the longest palindromic substring in s.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def is_Same(char_one: str, char_two: str) -> bool: | |
return char_one == char_two | |
class Solution: | |
def __init__(self): | |
#todo: could initialize some class vars like s_chars, s_pointer, s_pal_longest | |
pass | |
def longestPalindrome(self, s: str) -> str: | |
## total number of chars in s | |
s_chars = len(s) | |
## pointer to keep track of | |
s_pointer = 0 | |
## the longest palindromic substring in s | |
s_pal_longest = '' | |
while s_pointer < s_chars: | |
# the intervim var for each s_pointer eval | |
s_pal = '' | |
# Find the char of s_pointer | |
p_char = s[s_pointer] | |
# Find the char of s_pointer - 1 (left side) | |
if s_pointer - 1 > -1: | |
l_pointer = s_pointer - 1 | |
l_char = s[l_pointer] | |
else: | |
# there's nothing on the left move pointer forward and continue outter while | |
l_char = None | |
# s_pointer += 1 | |
# continue | |
# Find the char of s_pointer + 1 (right side) | |
if s_pointer + 1 < s_chars: | |
r_pointer = s_pointer + 1 | |
r_char = s[r_pointer] | |
elif l_char is not None: | |
# there's nothing on the right, evaluate just p_char & l_char and then continue | |
if is_Same(p_char, l_char): | |
s_pal = l_char + p_char | |
# now see if larger than existing s_pal_longest | |
if len(s_pal) > len(s_pal_longest): | |
s_pal_longest = s_pal | |
s_pointer += 1 | |
continue | |
else: | |
s_pointer += 1 | |
continue | |
else: | |
s_pointer += 1 | |
continue | |
else: | |
r_char = None | |
s_pointer += 1 | |
continue | |
# give p_char & r_char a check | |
if is_Same(p_char, r_char): | |
s_pal = ''.join([p_char, r_char]) | |
if len(s_pal) > len(s_pal_longest): | |
s_pal_longest = s_pal | |
# if left side and right side are equal then concat to s_pal | |
if is_Same(l_char, r_char): | |
s_pal = l_char + p_char + r_char | |
# move l_pointer and r_pointer along | |
l_pointer -= 1 | |
r_pointer += 1 | |
else: | |
s_pointer += 1 | |
continue | |
# while s_pointer - 1 and s_pointer + 1 are >= 0 and <= s_chars then keep checking | |
while (l_pointer > -1) and (r_pointer < s_chars): | |
l_char = s[l_pointer] | |
r_char = s[r_pointer] | |
if is_Same(l_char, r_char): | |
s_pal = ''.join([l_char, s_pal, r_char]) | |
l_pointer -= 1 | |
r_pointer += 1 | |
continue | |
else: | |
break | |
# once inner while broken compare if s_pal to s_pal_longest | |
if len(s_pal) > len(s_pal_longest): | |
s_pal_longest = s_pal | |
# move s_pointer along | |
s_pointer += 1 | |
if len(s_pal_longest) == 0: | |
return s[0] | |
return s_pal_longest |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment