题目描述

Alice 正在她的电脑上输入一个字符串。但是她打字技术比较笨拙，她 可能 在一个按键上按太久，导致一个字符被输入 多次。

尽管 Alice 尽可能集中注意力，她仍然可能会犯错 至多 一次。

给你一个字符串 word，它表示 最终 显示在 Alice 显示屏上的结果。

请你返回 Alice 一开始可能想要输入字符串的总方案数。

样例

输入：word = "abbcccc"

输出：5

解释：

可能的字符串包括："abbcccc"，"abbccc"，"abbcc"，"abbc" 和 "abcccc"。

输入：word = "abcd"

输出：1

解释：

唯一可能的字符串是 "abcd"。

输入：word = "aaaa"

输出：4

限制

• 1 <= word.length <= 100
• word 只包含小写英文字母。

算法

(分类讨论，双指针) $O(n)$

1. 显然，出现连续两个以上字符的情况才有可能犯错。
2. 对于每个连续两个以上的字符长度 $L$，可能犯错的方式有 $L - 1$ 种。
3. 最后再加一种不犯错的情况。

时间复杂度

• 双指针遍历字符串一次，故时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int possibleStringCount(string word) {
        const int n = word.size();

        int ans = 1;
        for (int i = 1, j = 0; i <= n; i++) {
            if (i < n && word[i] == word[j])
                continue;

            ans += i - j - 1;
            j = i;
        }

        return ans;
    }
};