求连续子串的权重

Question

我上周在技术评估时遇到了这个问题。我不知道我做错了什么。

给定一个大小为 n 的整数列表，找到权重范围为 1, 2, ..., n 的连续子串的数量。子字符串的权重是字符串包含的不同整数的数量。例如，权重('1') = 1，权重('1 1') = 1，权重('2 1') = 2。

当输入字符串为“1 1 2”时，输出将为“4 2 0”。 n 为 3，我们需要找到权重为 1、2、3 的子串的数量。对于权重为 1 的连续子串，有 4 个子串：'1'、'1'、'2' 和 1 1' 。对于权重为 2 的连续子串，有 2 个子串：'1 2' 和 1 1 2'。对于权重为 3 的连续子串，有 0 个子串。

我的Python代码只能通过40%的测试用例：

import collections
def substringWeights(s):
    n = len(s)
    substrings = []
    for i in range(n):
        for j in range(i+1, n+1):
            substrings.append(s[i:j])

    weight = collections.defaultdict(int)
    for i in range(1, n+1):
    weight[i] = 0

    for item in substrings:
        weightValue = len(set(item))
        weight[weightValue] += 1
    
    res = weight.values()
    res.sort(reverse = True)
    res = list(map(str, res))
    return ' '.join(res)

这里我首先生成所有子字符串，然后计算每个子字符串的weightValue并使用defaultdict记录数字。

不知道为什么我做错了。请帮忙！！！预先感谢！

Answer 1

我认为你可以使用滑动窗口的方法来使计算更加高效。对于 s 的每个 K 大小的子字符串（其中

1 <= K <= len(s)

），您可以使用字典创建一个从索引 0 开始到索引 K - 1 的 K 大小滑动窗口，以跟踪窗口中的唯一字符出现计数（

window

）下面的代码），然后迭代字符串（即

1 - K

->

2 - (K + 1)

-> ...），对于每次迭代，

window

字典减去前一个窗口的第一个字符，如果它为零则删除键。这样您就可以有效地跟踪 s 的每个可能子字符串的唯一字符计数，并随时更新权重计数

def substringWeights(s):
    weights = [0] * len(s)
    for i in range(1, len(s) + 1):
        window = collections.defaultdict(lambda : 0)
        for j in range(i):
            window[s[j]] += 1
        
        weights[len(window) - 1] += 1

        for j in range(i, len(s)):
            window[s[j - 1]] -= 1
            window[s[j]] += 1
            if window[s[j - 1]] == 0:
                window.pop(s[j - 1])
            weights[len(window) - 1] += 1
    return ' '.join([str(x) for x in weights])