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

Last updated