4

leetcode 828. 独特字符串

 2 years ago
source link: https://iamxcb.com/leetcode-828.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

leetcode 828. 独特字符串

发表于 2019-07-08

| 0

| 阅读次数:

如果一个字符在字符串 S 中有且仅有出现一次，那么我们称其为独特字符。
例如，在字符串 S = “LETTER” 中，”L” 和 “R” 可以被称为独特字符。
我们再定义 UNIQ(S) 作为字符串 S 中独特字符的个数。
那么，在 S = “LETTER” 中， UNIQ(“LETTER”) = 2。
对于给定字符串 S，计算其所有非空子串的独特字符的个数（即 UNIQ(substring)）之和。
如果在 S 的不同位置上出现两个甚至多个相同的子串，那么我们认为这些子串是不同的。
考虑到答案可能会非常大，规定返回格式为：结果 mod 10 ^ 9 + 7。

示例 1:
输入: “ABC”
输出: 10
解释: 所有可能的子串为：”A”,”B”,”C”,”AB”,”BC” 和 “ABC”。
其中，每一个子串都由独特字符构成。
所以其长度总和为：1 + 1 + 1 + 2 + 2 + 3 = 10

示例 2:
输入: “ABA”
输出: 8
解释: 除了子串 UNIQ(‘ABA’) = 1，其余与示例1相同。

说明: 0 <= S.length <= 10000。

首先子串的独特字符的个数和即 sum(UNIQ(substring))，可以转化为求解包含 S[i] 的子串中，S[i] 为独特字符的和即 sum(UNIQ(S[i])) ；
同时包含 S[i] 的子串中，可能会存在 S[i] 永远不会为独特字符的子串；
当 j < i && S[j] == S[i] 时，以 S[j] 开始的子串会使 S[i] 永远成不了独特字符；
当 k > i && S[k] == S[i] 时，以 S[k] 结尾的子串会使 S[i] 永远成不了独特字符；
所以可以去除这两种情况，在 S[j+1:k] 之间统计 UNIQ(S[i])；
最终问题就变成了计算在 S[j+1:k] 之间，包含 S[i] 的子串有多少种可能，因为每个子串中 S[i] 都会是独特字符；
在 S[j+1:k] 之间，包含 S[i] 的子串的数量其实就等于 (i - j) * (k - i)；
S[j+1:i+1], S[j+1:i+2], ..., S[j+1:k]，S[j+2:i+1], S[j+2:i+2], ...., S[j+1:k]，….，S[i:i+1], S[i:i+2], ...., S[i:k]

示例代码(go)

func uniqueLetterString(S string) int {
    res, n := 0, len(S)
    for i := 0; i < n; i++ {
        j, k := 0, 0
        for j = i-1; j >= 0; j-- {
            if S[j] == S[i] {
                break
            }
        }
        for k = i+1; k < n; k++ {
            if S[k] == S[i] {
                break
            }
        }
        res += (i - j) * (k - i)
    }
    return res
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK