Identity number which appears exactly once.

Similar Problems:

Given an integer array of size n, find all elements that appear more than n/3 times. The algorithm should run in linear time and in O(1) space.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution:

// Blog link: https://code.dennyzhang.com/longest-string-chain // Basic Ideas: LIS dp + hashmap // // Notice: instead of adding a character, try to delete one // The sequence doesn't matter: There might be a chain of s[i] -> s[j] with j<i // // Complexity: Time O(n*log(n)) Space O(n) import "sort" func longestStrChain(words []string) int { sort.Slice(words , func(i, j int) bool { return len(words[i])<len(words[j]) }) m := map[string]int{} dp := make([]int, len(words)) res := 0 dp[0] = 1 m[words[0]] = 0 for i:=1; i<len(words); i++ { word := words[i] max := 1 for j, _ := range word { word2 := word[0:j]+word[j+1:] if v, ok := m[word2]; ok { if dp[v]+1>max { max = dp[v]+1 } } } dp[i] = max m[word] = i if max > res { res = max } } return res }