# 2022-06-12

## [300. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/)

### Description

Given an integer array `nums`, return the length of the longest strictly increasing subsequence.

A **subsequence** is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, `[3,6,2,7]` is a subsequence of the array `[0,3,1,6,2,2,7]`.

**Example 1:**

```
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
```

**Example 2:**

```
Input: nums = [0,1,0,3,2,3]
Output: 4
```

**Example 3:**

```
Input: nums = [7,7,7,7,7,7,7]
Output: 1
```

**Constraints:**

* `1 <= nums.length <= 2500`
* `-10^4 <= nums[i] <= 10^4`

**Follow up:** Can you come up with an algorithm that runs in `O(n log(n))` time complexity?

### Solution

#### Approach #0

```go
func lengthOfLIS(nums []int) (ans int) {
    n := len(nums)
    dp := make([]int, n)
    dp[0] = 1
    ans = 1
    for i := 1; i < n; i++ {
        dp[i] = 1
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
        ans = max(ans, dp[i])
    }
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```

## [673. Number of Longest Increasing Subsequence](https://leetcode.com/problems/number-of-longest-increasing-subsequence/)

### Description

Given an integer array `nums`, return *the number of longest increasing subsequences.*

**Notice** that the sequence has to be **strictly** increasing.&#x20;

**Example 1:**

```
Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].
```

**Example 2:**

```
Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.
```

**Constraints:**

* `1 <= nums.length <= 2000`
* `-10^6 <= nums[i] <= 10^6`

### Solution

#### Approach #0

```go
func findNumberOfLIS(nums []int) (ans int) {
    n := len(nums)
    dp := make([]int, n)
    cnt := make([]int, n)
    maxLen := 0
    for i := 0; i < n; i++ {
        dp[i] = 1
        cnt[i] = 1
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] {
                if dp[j]+1 == dp[i] {
                    cnt[i] += cnt[j]
                }
                if dp[j]+1 > dp[i] {
                    dp[i] = dp[j] + 1
                    cnt[i] = cnt[j]
                }
            }
        }
        if dp[i] > maxLen {
            maxLen = dp[i]
            ans = cnt[i]
        } else if dp[i] == maxLen {
            ans += cnt[i]
        }
    }
    return
}
```

## [890. Find and Replace Pattern](https://leetcode.com/problems/find-and-replace-pattern/)

### Description

Given a list of strings `words` and a string `pattern`, return *a list of* `words[i]` *that match* `pattern`. You may return the answer in **any order**.

A word matches the pattern if there exists a permutation of letters `p` so that after replacing every letter `x` in the pattern with `p(x)`, we get the desired word.

Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.

**Example 1:**

```
Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output: ["mee","aqq"]
Explanation: "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}. 
"ccc" does not match the pattern because {a -> c, b -> c, ...} is not a permutation, since a and b map to the same letter.
```

**Example 2:**

```
Input: words = ["a","b","c"], pattern = "a"
Output: ["a","b","c"] 
```

**Constraints:**

* `1 <= pattern.length <= 20`
* `1 <= words.length <= 50`
* `words[i].length == pattern.length`
* `pattern` and `words[i]` are lowercase English letters.

### Solution

#### Approach #0

```go
func findAndReplacePattern(words []string, pattern string) (ans []string) {
    if len(pattern) == 1 {
        return words
    }
    for _, word := range words {
        if match(word, pattern) && match(pattern, word) {
            ans = append(ans, word)
        }
    }
    return
}

func match(word, pattern string) bool {
    m := make(map[rune]byte)
    for i, a := range word {
        b := pattern[i]
        if m[a] == 0 {
            m[a] = b
        } else {
            if m[a] != b {
                return false
            }
        }
    }
    return true
}
```