Double Pointers

5. Longest Palindromic Substring

Leetcode

Approach: There are two cases for the center of a palindrome:

1. The palindrome has odd length, i.e., the center is a single character.
2. The palindrome has even length, i.e., the center is two identical characters.

For each character in the string, we treat it as the center and expand outwards on both sides to find the longest palindrome centered at it and update the answer.

Example:

Input: s = “babad”
Output: “bab”
Explanation: “aba” is also a valid answer.

Solution:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        ans = ""
        for i in range(len(s)):
            # odd length case
            cur = self.findPalindrome(s, i, i)
            if len(cur) > len(ans):
                ans = cur
            # even length case
            # if s[i] and s[i+1] are not identical, it will return ""
            cur = self.findPalindrome(s, i, i+1)
            if len(cur) > len(ans):
                ans = cur
        return ans

    def findPalindrome(self, s: str, left: int, right: int):
        """
        Find the longest palindrome by starting from `left` and `right`
        and going outwards.
        """
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left+1: right]

26. Remove Duplicates from Sorted Array

Leetcode

Example:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]

Approach: Use a fast pointer j to iterate through the array, and a slow pointer i to keep track of update progress. If the current iterated element is equal to the previous one, skip it. Otherwise, update the slow pointer with the current element and move to the next position.

Solution:

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 0
        for j in range(len(nums)):
            if j > 0 and nums[j] == nums[j-1]:
                continue
            nums[i] = nums[j]
            i += 1
        return i

Note

For the skip condition highlighted above,

if j > 0 and nums[j] == nums[i-1]

also works (passes Leetcode) and might be more intuitive. At the beginning of each loop for j, check if the current iterated element is the same as the last updated element, i.e., nums[i-1].

80. Remove Duplicates from Sorted Array II

Leetcode

Example:

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]

Approach: Use a fast pointer j to iterate through the array, and a slow pointer i to keep track of the position to place the next unique element. Similar approach to the previous problem but beware of the wrong solution below, which yields wrong answer [1,1,2,3,_,_] for the example above. That is because in this problem we need to keep at most two of the duplicates and nums[j-2] is possible to have been updated already (when j-2<=i).

Solution:

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 0
        for j in range(len(nums)):
            if j > 1 and nums[j] == nums[j-2]:
            if j > 1 and nums[j] == nums[i-2]:
                continue
            nums[i] = nums[j]
            i += 1
        return i

Note

For the skip condition above, the following two versions both pass Leetcode:

if j > 1 and nums[j] == nums[i-2]

and

if i > 1 and nums[j] == nums[i-2]