统计只含单一字母的子串

Submission

运行时间: 26 ms

内存: 0.0 MB

class Solution:
    def countLetters(self, s: str) -> int:
        s += " "
        st = 0
        rst = 0
        for i in range(len(s)):
            if s[i] != s[st]:
                rst += (i-st) * (i-st+1) // 2
                st = i
        return rst

Explain

这个题解通过遍历字符串来计算所有只含单一字母的子串的数量。首先，在字符串末尾添加一个空格作为哨兵字符，以便处理字符串的最后一个字符组成的子串。使用变量`st`来标记当前连续字符子串的起始位置。循环中，当遇到与`st`位置字符不同的字符时，计算从`st`到当前位置前一个位置之间的子串数，使用公式`(i-st) * (i-st+1) / 2`进行计算，然后更新`st`为当前字符的位置。这种方法有效地利用了数学公式计算连续字符的组合方式，避免了多重循环，提高了效率。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def countLetters(self, s: str) -> int:
        s += ' '  # 添加哨兵字符，以便处理字符串末尾的情况
        st = 0  # 子串开始位置
        rst = 0  # 结果计数
        for i in range(len(s)):
            if s[i] != s[st]:
                rst += (i-st) * (i-st+1) // 2  # 计算当前片段的子串数量
                st = i  # 更新开始位置为新的字符位置
        return rst  # 返回结果

Explore

在字符串末尾添加一个哨兵字符（空格）是为了简化代码逻辑，避免在循环结束后再单独处理最后一个连续字符的子串。这种做法确保在遍历完成时，即使是字符串的最后一个字符组成的连续子串也能被正确统计。当循环遍历到这个哨兵字符时，由于它和前一个字符一定不同，会触发计算从`st`到当前字符前一个位置的子串数量的逻辑，从而处理完所有字符。

这个公式用于计算从位置`st`到位置`i-1`之间，所有可能的只含单一字母的子串的数量。若字符段的长度为`n`（即`i-st - 1`），该段可以形成的连续子串长度可以是1到`n`。每种长度的子串的数量分别是`n, n-1, ..., 1`。总和可以通过求和公式`n(n+1)/2`计算得出。因此，公式`(i-st) * (i-st+1) / 2`实际上是计算从`st`到`i-1`的连续相同字符可以组成的所有可能子串的数量，这是一个数学上的组合问题解决方案。

是的，如果输入字符串为空，算法仍然能正确返回结果0。在这种情况下，空字符串在添加哨兵字符后变为' '。循环将从索引0开始，但由于哨兵字符与任何字符都不相同，`st`将立即更新为1，不会进行任何子串计数，因此`rst`保持为0，最终返回0。

在算法中，每次遇到新的字符或哨兵字符时，都会计算上一个连续字符子串的所有可能的子串数量，并将这个数量累加到`rst`。由于每一段的计算都是通过`(i-st) * (i-st+1) / 2`完成，保证了计算时不会超出整型范围。然而，在极大的输入字符串或极长的相同字符序列情况下，累加的结果可能会超过整数可表示的范围，导致数据溢出。在实际应用中，需要根据预期输入大小选择合适的数值类型（如使用长整型`long`）以避免溢出。