同端子串的数量

Submission

运行时间: 799 ms

内存: 33.5 MB

class Solution:
    def sameEndSubstringCount(self, s: str, queries: List[List[int]]) -> List[int]:
        n = len(s)
        result = list()
        counters = [[0]*26]
        for c in s:
            tmp = counters[-1].copy()
            tmp[ord(c)-ord('a')] += 1
            counters.append(tmp)
        for x, y in queries:
            tmp = 0
            for i in range(26):
                v = counters[y+1][i] - counters[x][i]
                tmp += v * (v + 1) // 2
            result.append(tmp)
        return result

Explain

此题解采用前缀和数组来快速计算字符串中任意子串的字符频率。首先，构建一个前缀和数组counters，其中counters[i][j]表示字符串s中前i个字符中字符('a'+j)出现的次数。接着，对于每个查询，我们可以快速得到子串s[x...y]中每个字符的出现次数，然后计算每个字符能形成的同端子串的数量，即字符出现次数乘以该次数加一再除以二。最后，将这些数相加得到对应查询的结果。

时间复杂度: O(n + q)

空间复杂度: O(n)

class Solution:
    def sameEndSubstringCount(self, s: str, queries: List[List[int]]) -> List[int]:
        n = len(s)
        result = list()
        counters = [[0]*26]  # 创建一个二维数组，存储字符的前缀和
        for c in s:
            tmp = counters[-1].copy()  # 复制上一个前缀数组
            tmp[ord(c)-ord('a')] += 1  # 更新当前字符的计数
            counters.append(tmp)  # 将更新后的数组加入counters
        for x, y in queries:
            tmp = 0
            for i in range(26):
                v = counters[y+1][i] - counters[x][i]  # 计算x到y子串中每个字符的出现次数
                tmp += v * (v + 1) // 2  # 计算同端子串的数量并累加
            result.append(tmp)  # 将结果存储到结果列表
        return result

Explore

在构建前缀和数组时，每次我们遍历字符串s的一个字符，都会复制上一个前缀数组并对当前字符的计数进行更新。这个更新是单步、直接的加法操作，因此只要程序逻辑正确，就不会出现计数误差。我们从第一个字符到最后一个字符一次处理，保证每一步的计数都是建立在前一步准确结果的基础上的。

前缀和数组counters的初始化为[[0]*26]表示在字符串s的开始前，即位置0之前，所有26个英文字母的出现次数都是0。这是为了确保在计算字符串任意前缀的字符频率时，我们可以直接使用counters数组而无需考虑边界条件。例如，要计算从字符串开始到某位置y的某字符的频率，可以直接查看counters[y+1]。

前缀和数组通过counters[y+1][i]表示从字符串开始到位置y（包括y）的字符i的出现次数，而counters[x][i]表示从字符串开始到位置x-1的字符i的出现次数。因此，counters[y+1][i] - counters[x][i]正好给出了从位置x到位置y的子串中字符i的出现次数。这个计算方法是基于前缀和的性质，确保了计算的准确性。

当一个字符在子串中出现v次时，可以形成从1到v的所有可能的子串长度的同端子串。例如，字符连续出现3次，可以形成长度为1的子串3个，长度为2的子串2个，长度为3的子串1个，总共6个。这可以通过求和公式v*(v+1)/2来计算，该公式实际上是计算从1加到v的自然数的和，每个自然数代表该长度的同端子串的数量。