計算由單一不同字元組成的子字串的數量

在本文中，我們將討論計算給定字串中由單一不同字元組成的子字串數量的問題。我們將探索一種有效的演算法來解決這個問題，並提供 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中文網其他相關文章！