数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学统计由单个不同字符组成的子字符串个数
在本文中，我们将讨论计算给定字符串中由单个不同字符组成的子字符串个数的问题。我们将探讨解决此问题的有效算法，并提供C++代码来实现它。
问题陈述
给定一个字符串S，任务是计算由单个不同字符组成的子字符串的个数。
例如，如果输入字符串是“aaaaa”，则输出应为15，因为有15个子字符串由单个不同字符组成。这些子字符串是“a”，“a”，“a”，“a”，“a”，“aa”，“aa”，“aa”，“aa”，“aaa”，“aaa”，“aaa”，“aaaa”，“aaaa”，“aaaaa”。
算法
我们可以在线性时间复杂度内解决这个问题。我们可以遍历输入字符串，并跟踪当前字符和当前子字符串的长度。每当我们遇到一个新字符或到达字符串的末尾时，我们可以计算可以使用当前字符和当前子字符串的长度形成的子字符串的个数。
以下是解决此问题的逐步算法：
将count和len初始化为1。
从索引1到n-1遍历字符串S。
如果当前字符与前一个字符相同，则将len加1。
如果当前字符与前一个字符不同，则将(len*(len+1))/2加到count中，并将len重置为1。
返回count。
让我们以字符串“aaaaa”为例来理解该算法：
将count和len初始化为1。
从索引1到n-1遍历字符串
在索引1处，当前字符与前一个字符相同，因此将len加1。
在索引2处，当前字符与前一个字符相同，因此将len加1。
在索引3处，当前字符与前一个字符相同，因此将len加1。
在索引4处，当前字符与前一个字符相同，因此将len加1。
我们已经到达字符串的末尾，因此将(len*(len+1))/2加到count中。count = count + (5*(5+1))/2 = 15。
返回count。
C++实现
以下是实现上述算法的C++代码：
示例
以下是实现上述算法的程序：
#include <stdio.h>
#include <string.h>
int countSubstrings(char S[]) {
int n = strlen(S);
int count = 1, len = 1; // Initialize counters for substrings and consecutive characters
for (int i = 1; i < n; i++) {
if (S[i] == S[i - 1]) { // Check if the current character is the same as the previous one
len++; // If yes, increment the length of consecutive characters
} else {
count += (len * (len + 1)) / 2; // Calculate and accumulate substrings formed by consecutive characters
len = 1; // Reset the length for new set of consecutive characters
}
}
count += (len * (len + 1)) / 2; // Account for the last set of consecutive characters
return count - 1; // Return the total count of substrings
}
int main() {
char S[] = "aaaaa";
int count = countSubstrings(S);
printf("%d\n", count);
return 0;
}
输出
15
#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
public class SubstringCounter {
public static int countSubstrings(String S) {
int n = S.length(); // length of the input string
int count = 1, len = 1; // Initialize counters for substrings and consecutive characters
for (int i = 1; i < n; i++) {
if (S.charAt(i) == S.charAt(i - 1)) { // Check if the current character is the same as the previous one
len++; // If yes, increment the length of consecutive characters
} else {
count += (len * (len + 1)) / 2; // Calculate and accumulate substrings formed by consecutive characters
len = 1; // Reset the length for new set of consecutive characters
}
}
count += (len * (len + 1)) / 2; // Account for the last set of consecutive characters
return count - 1; // Return the total count of substrings
}
public static void main(String[] args) {
String S = "aaaaa";
int count = countSubstrings(S);
System.out.println(count);
}
}
输出
15
def count_substrings(S):
n = len(S)
count = 1 # Initialize counters for substrings
length = 1 # Initialize counter for consecutive characters
for i in range(1, n):
if S[i] == S[i - 1]: # Check if the current character is the same as the previous one
length += 1 # If yes, increment the length of consecutive characters
else:
count += (length * (length + 1)) // 2 # Calculate and accumulate substrings formed by consecutive characters
length = 1 # Reset the length for new set of consecutive characters
count += (length * (length + 1)) // 2 # Account for the last set of consecutive characters
return count - 1
def main():
S = "aaaaa"
count = count_substrings(S) # Call the function to count substrings
print(count)
if __name__ == "__main__":
main()
输出
15
结论
在本文中，我们讨论了计算给定字符串中由单个不同字符组成的子字符串个数的问题。我们提供了一个有效的算法，可以在线性时间复杂度内解决此问题，并用C++实现了它。这个问题也可以使用其他技术来解决，但是上述算法提供了
201 次查看
