# 2022-06-10

## [5. Longest Palindromic Substring](https://leetcode.com/problems/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

```go
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](https://leetcode.com/problems/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

```go
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

```go
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
}
```