Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

1 <= text1.length, text2.length <= 1000

text1 and text2 consist of only lowercase English characters.

Solution

Approach #0

funclongestCommonSubsequence(text1 string, text2 string) int { m, n :=len(text1), len(text2) dp :=make([][]int, m+1)for i :=0; i < m+1; i++ { dp[i] =make([]int, n+1) }for i, c1 :=range text1 {for j, c2 :=range text2 {if c1 == c2 { dp[i+1][j+1] = dp[i][j] +1 } else { dp[i+1][j+1] =max(dp[i][j+1], dp[i+1][j]) } } }return dp[m][n]}funcmax(a, b int) int {if a > b {return a }return b}

A school is trying to take an annual photo of all the students. The students are asked to stand in a single file line in non-decreasing order by height. Let this ordering be represented by the integer array expected where expected[i] is the expected height of the ith student in line.

You are given an integer array heights representing the current order that the students are standing in. Each heights[i] is the height of the ith student in line (0-indexed).

Return the number of indices where heights[i] != expected[i].

Example 1:

Input: heights = [1,1,4,2,1,3]
Output: 3
Explanation:
heights: [1,1,4,2,1,3]
expected: [1,1,1,2,3,4]
Indices 2, 4, and 5 do not match.

Example 2:

Input: heights = [5,1,2,3,4]
Output: 5
Explanation:
heights: [5,1,2,3,4]
expected: [1,2,3,4,5]
All indices do not match.

Example 3:

Input: heights = [1,2,3,4,5]
Output: 0
Explanation:
heights: [1,2,3,4,5]
expected: [1,2,3,4,5]
All indices match.

Constraints:

1 <= heights.length <= 100

1 <= heights[i] <= 100

Solution

Approach #0

funcheightChecker(heights []int) (ans int) { expected :=append([]int(nil), heights...) sort.Ints(expected)for i, h :=range heights {if h != expected[i] { ans++ } }return}

Approach #1

funcheightChecker(heights []int) (ans int) { cnt :=make([]int, 101)for _, h :=range heights { cnt[h]++ } index :=0for i, c :=range cnt {for ; c >0; c-- {if heights[index] != i { ans++ } index++ } }return}