LongestPalindromicSubStringwithmyownfullexplanationlinebyline

5. Longest Palindromic Substring
Medium
25.8K
1.5K
Companies
Given a string s, return the longest 
palindromic
 
substring
 in s.

 

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Example 2:

Input: s = "cbbd"
Output: "bb"
 

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters.

Solution in Python:

#control flow line by line explanation for the s = "babad" case

class Solution(object):
    def longestPalindrome(self, s):
        def helper(left, right): #left and right do no have values. the values of left and right will be determined by the for loop, which will be passed to helper(i, i), which will then be passed back to left, and right in the same position, giving left and right values of 0 and 0 on the 1st iteration. 0 and 0 are within boundary checks, so decrement left and increment right to make left = -1 and right = 1. Now, the while loop boundary check fails, so return b in babad because s[left + 1, right] means up to but not including right, so if right is 1, we would include up to the 0th index character, and left + 1 means above left, so b is the return value, and TEST ALSO BECOMES b, not result YET. Next, we would go to if len(test) > len(result), which means that it is true since b has a greater length than "", so NOW result gets updated from "" to b. Next, test = helper(i, i + 1) is called, giving left a value of 0 and right a value of 1 since the i value of 0 never changed, so left stays 0, but right is i + 1, so 0 + 1 = 1. Now, def(left, right) gets invoked with an actual value this time (left being 0 and right being 1), and the while loop boundary checks fail not because of the boundary, but because left DOES NOT EQUAL right, so it's not a valid palindromic substring. Since we have left = 0 and right = 1 and we are executing return since the while loop exaluated to false, and we have s[left + 1, right] meaning 0 + 1, 1 (up to but not including), we are actually returning "", and "" becomes the value of test in test = helper(i, i + 1). Now, we go down to the if len(test) > len(result) after test = helper(i, i + 1) case, and len of "" is not greater than len (b), so go back to the for i in range(len(s)), and i goes from 0 to 1 because i increments everytime this for loop is invoked. We go down one line to test = helper(i, i), and since i = 1, we go back to def helper(left, right), and left = 1 and right = 1. the 3rd line while loop boundary check and equality of s[left] and s[right] VALUES NOT INDEXES pass, so execute lines 4 and 5 to decrement left and increment right. left is now 0, and right is now 2, and we invoke the while loop in line 3 again, and, again, the while loop boundary check passes as left is 0, right is 2, and the values corresponding to those indexes match, so execute lines 4 and 5 to decrement left and increment right. left is now -1, and right is now 3, This fails the 3rd line while loop boundary check, so invoke the line at the very next indent - return s[left + 1, right]. so we are now returning "bab" from the original s value of "babad" since left + 1 = -1 + 1 = index 0, and up to but not including right, so 2 is right's last value, so "bab" from the original s = "babad" substring gets returned. the return s[left + 1, right] value gets passed to test = helper(i, i), so test now becomes "bab", and since we were on a test = helper(i, i) case, we invoke the "if len(test) > len(result)" right below it. len of "bab" is greater than len of "b", so result gets updated to test, so result goes from historical greatest "b" to "bab", and since if blocks execute the line at same indentation after executing the inner block, we invoke test = helper(i, i + 1), which invokes def(left, right) again in line 2, and since i's value of 1 hasn't changed, left = 1, and right = 2. left as 1 and right as 2 fail trigger the while loop to evulate as false since index 1's value and index 2's value in the original s = "babad" string are not equal, so we execute the block at the next indentation - return s[left + 1, right], and left = 1, so 1 + 1 = 2, and right = 2, so since right is not included, we are actually returning "" from return s[left + 1, right], setting the corresponding test = helper(i, i + 1)'s value to "". the line below test = helper(i, i + 1) is invoked - if len(test) > len(result), and since the len of "" isn't bigger than the len of "bab", the if statement evaluates to false, and the for loop is invoked again - for i in range(len(s)), this time, incrementing i from 1 to 2 as i is incremented by 1 up to but not including the length of s everytime this for loop is invoked. The next line - test = helper(i, i) is invoked, passing 2 and 2 and calling def(left, right) in line 2, giving left a value of 2 and right a value of 2. This passes the line 3 while loop's boundary check and the value at the 2nd indexes' check, so continue to decrement left and increment right there in lines 4 and 5, taking left from 2 to 1 and right from 2 to 3, so left = 1 now and right = 3 now. We haven't finished the while loop yet, just like before, so the 3rd line while loop is invoked yet again, and it passes the boundary and value checks again, so execute lines 4 and 5 yet again, changing left from 1 to 0 and right from 3 to 4, giving left a value of 0 and right a value of 4. Now, the line 3 while loop boundary and value check fail because indexes 0 and 4 are not equal when they are processed into values in the original s = "babad" string with 0 being "b" and 4 being "d", so the return s[left + 1, right] is invoked because it is the next line at the same indentation as the failed while loop in line 3. BTW, we are now on step 52 out of 93. return s[left + 1, right] turns into s[0 + 1, 4], which turns into s[1, 4], which is indexes 1 up to 3 inclusive in the original s ="babad", so we get "aba" from this return s[left + 1, right], and then we pass "aba" as the value to test = helper(i, i), giving the test variable a value of "aba". Next, we call the line right below test = helper(i, i), which is if len(test) > len(result), and, in this case, len of "aba" (test) is equal to the historical len of "bab" (result), WHICH MAKES IF LEN(TEST) > LEN(RESULT) FALSE, SINCE IT'S BIGGER THAN NOT EQUAL TO, AND THE IF STATEMENT EVALUATES TO FALSE, SO WE INVOKE test = helper(i, i + 1). i from the for loop is still 2, giving test = helper(i, i + 1) a value of test = helper(2, 3), and then line 2 def(left, right) is called and passed in values as left = 2 and right = 3. line 3 while loop boundary and value check is invoked, and, while the boundary check is fine, the s[left] == s[right] condition of the while loop fails since s[2] == s[3] indexes turned into value value check inside the original s = "babad" is false as s[2] = "b", and s[3] == "a", so the return s[left + 1, right] is invoked, and s[2 + 1, 3] becomes s[3, 3], and since it starts and includes index 3 but goes up to but DOES NOT include the right index number, we return "" from return s[left + 1, right] in this case, giving test = helper(i, i + 1) a test variable value of "", and we proceed to invoked if len(test) > len(result), so len of "" > len of "bab" is false, making the if len(test) > len(result) condition false, so invoke the for i in range(len(s)) again, incrementing i's value from 2 to 3, so i = 3. Next, test = helper(i, i) is invoked, giving test variable a value of test = helper(3, 3), and valling def(left, right), giving line 2's def(left, right) a left value of 3 and a right value of 3. left = 3 and right = 3 pass the 3rd line while loop's boundary check and value check since we are using the same index to compute the same value and compare the values in the original s = "babad" string, so proceed to decrement left and increment right, taking left from 3 to 2 and right from 3 to 4, so left = 2 and right = 4 now. line 3's while loop boundary and value check are invoked again, this time, failing the value check as s[2] and s[4] are not equal in the original s = "babad" string with s[2] being "b" and s[4] being "d", so return s[left + 1, right] is invoked, giving us s[2 + 1, 4], giving us s[3, 4], so return s[3] inside of the original s = babad" makes the output of return s[left + 1, right] equal to "a", so test variable's value from test = helper(i, i) becomes "a", so test = "a", and the next if len(test) > len(result) comparison is now invoked, and len of "a" > len of the historical "bab" makes the if statement false, so skip down to the next block at the same indentation, skipping the if's inner block since it evaluated to false, so test = helper(i, i + 1) is now invoked, giving test = helper(i, i + 1) a value of test = helper(3, 3 + 1) equaling test = helper(3, 4) as the i value from the for i in range(len(s)) stayed as 3. test = helper(3, 4) calls line 2's def helper(left, right) to get def helper(3, 4) to give left and right values of 3 and 4, respectively. Next, line 3's while loop boundary and value check is invoked, and s[3] and s[4] are not equal in the original s = "babad" with s[3] equaling "a" and s[4] equaling "d", making the while loop in line 3 evaluate to false, so return s[left + 1, right] in line 6 is called, giving us s[3 + 1, 4], giving us s[4, 4], and since we start from and include the left value but up to and not including the right value, return s[left + 1, right] with s[4, 4] outputs a value of "", and "" becomes the value of the test variable in test = helper(i, i + 1), so test = "", and we proceed to check if len(test) > len(result), which is the line right after test = helper(i, i + 1), and len "" > len "bab" makes this if len(test) > len(result) if statement evaluate to false, so we call the for i in range(len(s)) to increment i from 3 to 4, and we go on to execute the very next line "test = helper(i, i), pass test = helper(i, i) as test = (4, 4), and calling the line 2 def(left, right) function and passing the values as def(4, 4), giving left = 4 and right = 4 the respective values of 4 and 4 for left and right. Next, the while loop check in 3 for boundary and values is called, and s[4] equals s[4] in the original s = "babad", so we continue to the next lines 4 and 5 to decrement left and increment right, taking left from 4 to 3 and right from 4 to 5, so left is now 3 and right is now 5. This fails the boundary check of while loop in line 3 since 4 is the last index in the original s = "babad", so call return s[left + 1, right], so s[3 + 1, 5] becomes s[4, 5] which includes 4 but doesn't and goes up to and dosen't include 5 which becomes "d" in the original s = "babad", giving return s[left + 1, right] and output value of "d". "d" gets passed as the value to the test variable in test = helper(i, i), so test = "d". we proceed to the next line if len(test) > len(result), and len of "d" > len of the historical result "bab" is false, so we go to the next line at the sam eindentation of the if statement to call test = helper(i, i + 1). i's value stays 4 from the for i in range(len(s)) loop, so test = helper(i, i + 1) becomes test = helper(4, 5), and the line 2 def(left, right) function is called, equaling def(4, 5), giving left a value of 4 and right a value of 5. the 3rd line while loop boundary check and value check is now invoked, and 5 fails the boundary check as there is no 5th index in the original s = "babad", so return s[left + 1, right] is called, so s[4 + 1, 5] becomes s[5, 5], which outputs "", and we go down to the if len(test) > len(result) right after the test = helper(i, i + 1) with test passed as "" from return in this case. len "" > len of the historical "bab: makes the if len(test) > len(result) statement evaluate to false, so call the for i in range(len(s)) to increment i from 4 to 5, since i = 5 now, and for 5 in range(len("babad")) is false, we jump to the next line at the same indentation, which is return result, with the historical result being "bab" in the s = "babad" case.  
            while (left >= 0 and right < len(s) and s[left] == s[right]): #boundary checks to make sure both pointers are still within the grid
                left -= 1 
                right += 1
            return s[left + 1: right]
        
        result = ""
        for i in range(len(s)):
            test = helper(i, i)
            if len(test) > len(result): 
                result = test #new max result is updated 
            test = helper(i, i + 1)
            if len(test) > len(result):
                result = test
        
        return result


#1/11/24 refresher:

class Solution:
    def longestPalindrome(self, s):
        def f(l, r, s):
            while l >= 0 and r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
            return s[l + 1: r] #s[including: not including] - not including is basically like minus 1
        res = ""
        for char in range(len(s)):
            first = f(char, char, s)
            if len(first) > len(res):
                res = first
            second = f(char, char + 1, s)
            if len(second) > len(res):
                res = second
        return res