2022-06-10

5. Longest Palindromic Substring

Description

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

Approach #0

func longestPalindrome(s string) string {
    n := len(s)
    if n < 2 {
        return s
    }
    dp := make([][]bool, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]bool, n)
        dp[i][i] = true
    }

    maxLen := 1
    start := 0

    for c := 2; c <= n; c++ {
        for i := 0; i < n; i++ {
            j := c + i - 1
            if j >= n {
                break
            }

            if s[i] != s[j] {
                dp[i][j] = false
            } else {
                if j-i < 3 {
                    dp[i][j] = true
                } else {
                    dp[i][j] = dp[i+1][j-1]
                }
            }

            if dp[i][j] && j-i+1 > maxLen {
                maxLen = j - i + 1
                start = i
            }
        }
    }
    return s[start : start+maxLen]
}

413. Arithmetic Slices

Description

An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

• For example, [1,3,5,7,9], [7,7,7,7], and [3,-1,-5,-9] are arithmetic sequences.

Given an integer array nums, return the number of arithmetic subarrays of nums.

A subarray is a contiguous subsequence of the array.

Example 1:

Input: nums = [1,2,3,4]
Output: 3
Explanation: We have 3 arithmetic slices in nums: [1, 2, 3], [2, 3, 4] and [1,2,3,4] itself.

Example 2:

Input: nums = [1]
Output: 0

Constraints:

• 1 <= nums.length <= 5000

• -1000 <= nums[i] <= 1000

Solution

Approach #0: Too much memory used

func numberOfArithmeticSlices(nums []int) (ans int) {
    n := len(nums)
    if n < 3 {
        return 0
    }
    v := make([]int, n-1)
    for i := 0; i < n-1; i++ {
        v[i] = nums[i+1] - nums[i]
    }

    for c := 3; c <= n; c++ {
        for i := 0; i < n; i++ {
            if i+c > n {
                break
            }
            p := true
            for j := i; j < i+c-2; j++ {
                p = p && v[j] == v[j+1]
                if !p {
                    break
                }
            }
            if p {
                ans++
            }
        }
    }
    return
}

Approach #1

func numberOfArithmeticSlices(nums []int) (ans int) {
    n := len(nums)
    if n == 1 {
        return
    }
    d, t := nums[1]-nums[0], 0
    for i := 2; i < n; i++ {
        if nums[i]-nums[i-1] == d {
            t++
        } else {
            d, t = nums[i]-nums[i-1], 0
        }
        ans += t
    }
    return
}