计算由单个不同字符组成的子字符串的数量

在本文中，我们将讨论计算给定字符串中由单个不同字符组成的子字符串数量的问题。我们将探索一种有效的算法来解决这个问题，并提供 C++ 代码来实现它。

问题陈述

给定一个字符串 S，任务是计算由单个不同字符组成的子字符串的数量。

例如，如果输入字符串为“aaaaa”，则输出应为 15，因为有 15 个子字符串由单个不同字符组成。子字符串为“a”、“a”、“a”、“a”、“a”、“a”、“a”、“a”、“a”、“a”、“a”、“aaa” 、“aaa”、“aaaa”、“aaaa”、“aaaa”。

算法

我们可以用线性时间复杂度解决这个问题。我们可以迭代输入字符串并跟踪当前字符和当前子字符串的长度。每当遇到新字符或者到达字符串末尾时，我们就可以统计当前字符可以组成的子串数量以及当前子串的长度。

这是解决这个问题的分步算法 -

• 将 count 和 len 初始化为 1。

• 从索引 1 到 n-1 迭代字符串 S。

• 如果当前字符与前一个字符相同，则 len 加 1。

• 如果当前字符与前一个字符不同，则添加 (len*(len+1))/2 进行计数，并将 len 重置为 1。

• 返回计数。

让我们以字符串“aaaaa”为例来理解算法 -

• 将 count 和 len 初始化为 1。

• 从索引 1 到 n-1 迭代字符串：

• 在索引 1 处，当前字符与前一个字符相同，因此 len 增加 1。

• 在索引 2 处，当前字符与前一个字符相同，因此 len 增加 1。

• 在索引 3 处，当前字符与前一个字符相同，因此 len 增加 1。

• 在索引 4 处，当前字符与前一个字符相同，因此 len 增加 1。

• 我们已到达字符串末尾，因此添加 (len*(len+1))/2 进行计数。计数 = 计数 + (5*(5+1))/2 = 15。

• 返回计数。

C++ 实现

这是实现上述算法的 C++ 代码 -

示例

#include<bits/stdc++.h>
using namespace std;

int countSubstrings(string S) {
   int n = S.length();
   int count = 1, len = 1;
   for (int i = 1; i < n; i++) {
      if (S[i] == S[i-1]) {
         len++;
      } else {
         count += (len*(len+1))/2;
         len = 1;
      }
   }
   count += (len*(len+1))/2;
   return count-1;
}

int main() {
   string S = "aaaaa";
   int count = countSubstrings(S);
   cout << count << endl;
   return 0;
}

输出

15

结论

在本文中，我们讨论了计算给定字符串中由单个不同字符组成的子字符串数量的问题。我们提供了一种有效的算法来以线性时间复杂度解决这个问题，并用 C++ 实现它。这个问题也可以使用其他技术来解决，但是上面的算法提供了

以上是计算由单个不同字符组成的子字符串的数量的详细内容。更多信息请关注PHP中文网其他相关文章！