5. Longest Palindromic Substring

Problem Statement

link: LeetCode.cn LeetCode Given a string s, return the longest palindromic substring in s.

Example:

Input: s = "babad" Output: bab

Input: s = "cbbd" Output: bb

Solution Approach

The solution utilizes a hashmap to keep track of the cumulative sum of ones and zeros in the input list, updating the maximum length when encountering matching cumulative sums.

Algorithm

1. Track the cumulative sum while traversing the list, incrementing for 1 and decrementing for 0.
2. Store the index of the first occurrence of each cumulative sum in a hashmap.
3. Update the maximum length of contiguous subarrays with equal cumulative sums and return the final result.

Implement

    class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        # 0 1 1 1 1 1 0 1 0 1
        # l.  r         
        #.  1 1
        # prex_r  - prex_l == 0  max: r - l + 1 , res
        l = 0
        curr = 0
        res = 0
        position = {0: -1}
        for r, n in enumerate(nums):
            curr += 1 if n else -1
            if curr in position: 
                res = max(res, r - position[curr])
            else:
                position[curr] = r 
        return res

    
    

Twitter  facebook  Email