列印給定字串中相鄰重複字元的頻率

---

字串是一種資料結構，由一系列字元組成。字串的結尾用一個特殊的字元標記，稱為空字元，通常用 ASCII 碼 0 表示。

問題陳述

給定一個特定長度的字串 s，手頭的任務是列印相鄰重複字元及其重複次數。

例如

Input: s = “committee”
Output: [[m, 2], [t, 2], [e, 2]]

解釋

字元 m 連續出現兩次。類似地，字元 t 和 e 也連續出現兩次。因此，我們返回包含這些字元及其各自重複次數的配對向量。

Input: s = “kkbkkk”
Output: [[k,2], [k,3]]

解釋

字元 k 連續出現兩次，因此我們將其新增到答案向量中。它後面跟著字元 b，該字元沒有重複出現，因此我們不將其包含在答案中。此外，字元 k 再次重複自身，因此我們將其與新的重複次數一起追加到答案中。

Input: s = “abcdae”
Output: []

解釋

字串 s 中沒有字元連續重複。因此，我們返回一個空的配對向量作為我們的最終答案。

解決方案方法

問題陳述非常簡單，解決方案方法也緊隨其後。其思想是簡單地遍歷給定字串並檢查下一個字元是否與當前字元相同。

如果是這種情況，則將字元的當前頻率增加 1。繼續此過程，直到我們到達一個新字元。此時，我們只需檢查前一個字元是否重複出現，如果重複出現，則將包含字元及其頻率的配對新增到我們的答案配對向量中。

否則，如果字元沒有重複出現，我們只需迭代到下一個字元並遵循相同的過程。

此解決方案線上性時間內工作。可以透過下面提供的虛擬碼和演算法更好地理解它。

虛擬碼

• 宣告一個配對向量“ans”來儲存最終結果。

• 初始化一個整數變數“curr_freq”，它將儲存字元當前重複的頻率。

• 宣告一個字元變數“prev_ele”，它將儲存字串中當前元素之前的元素，我們正在計算其頻率。

• 迭代字串

• 如果 prev_ele == 當前元素，則遞增 curr_freq

• 否則

• 如果 curr_freq > 1，則將 {prev_ele, curr_freq} 追加到 ans

• 重置 curr_freq

• 更新 prev_ele

• 返回 ans

演算法

• 函式 repeating_element()

• 初始化 curr_freq = 1

• 初始化 prev_ele = s[0]

• 對於 (i: 1 到 n - 1)

• 如果 (s[i] == prev_ele)

• curr_freq ++

• 否則

• 如果 (curr_freq > 1)

• ans.push_back({prev_ele, curr_freq})

• prev_ele = s[i]

• curr_freq = 1

• 如果 (curr_freq > 1)

• ans.push_back({prev_ele, curr_freq})

• 返回 ans

函式 main()

• 初始化字串 s

• 宣告 vector<pair<char,int>>ans

• 如果 (s.length() == 0) 返回 0;

• 函式呼叫 repeating element(s, ans)

• 列印 ans

示例：C++ 程式程式碼

以下 C++ 程式返回一個包含字串中所有連續出現超過一次的元素的配對向量，以及它們的重複次數。它宣告一個包含 char 和 int 的配對向量來儲存最終答案。我們進行函式呼叫 repeating_element() 並透過引用將字串和 ans 向量傳遞給它。

該函式使用 2 個變數 curr_freq 和 prev_ele 查詢並存儲連續重複的元素。然後我們簡單地列印 ans 向量。

// C++ program to print the characters of a given string which repeat themselves consecutively along with the frequency of their repetition
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using namespace std;
// the function adds the pair of repeating element and its freq to ans vector
void repeating_element(string & s, vector<pair<char, int>> & ans){
   int curr_freq = 1;
   char prev_ele = s[0];
   // loop to iterate over all the characters in the string and add pair of repeating characters and their frequency to ans vector
   for (int i = 1; i < s.length(); i++){
      // if current character matches prev_ele, increment its frequency of occurrence
      if (s[i] == prev_ele){
      curr_freq++;
      }
      else{
         // if the frequency of previous element is greater than 1, add it to ans vector
         if (curr_freq > 1){
            ans.push_back(make_pair(prev_ele, curr_freq));
         }
         // reset the curr_freq to 1 and update the previous element to current element
         curr_freq = 1;
         prev_ele = s[i];
      }
   }
   // to check if there is a repeating character at the end
   if (curr_freq > 1){
      ans.push_back(make_pair(prev_ele, curr_freq));
   }
   return;
}

int main(){
   string s = "committee";
   vector<pair<char, int>> ans;
   if (s.length() == 0)
   return 0;
   repeating_element(s, ans);
   for (auto & x : ans){
      cout << x.first << " : " << x.second;
      cout << endl;
   }
   return 0;
}

輸出

m : 2
t : 2
e : 2

時間和空間複雜度分析

時間複雜度 - O(n)

• repeating_element 函式 -

• 一個 for 迴圈遍歷輸入字串 s 的字元。令 n 為字串的長度。迴圈從索引 1 迭代到 n-1，因此它執行 n-1 次迭代。每次迭代都執行恆定時間操作（比較、遞增和推入向量）。因此，此迴圈的時間複雜度為 O(n)。

• main 函式 -

一個 for 迴圈遍歷 ans 向量中的元素以列印它們。此迴圈中的迭代次數取決於在輸入字串中找到的重複字元的數量。在最壞的情況下，如果字串中的所有字元都重複，這意味著迴圈迭代 n/2 次。因此，此迴圈的時間複雜度為 O(n/2)

.

總的來說，程式碼的時間複雜度為 O(n + n/2) = O(n)。

空間複雜度 - O(n)

• ans 向量 -

該向量儲存重複字元及其頻率的配對。在最壞的情況下，如果字串中的所有字元都是唯一的，則向量的大小可能為 n/2，因為每個重複字元都儲存一次。因此，ans 向量空間複雜度為 O(n)。

因此，程式碼的空間複雜度為 O(n)。

結論

本文討論了一種簡單的線性時間和空間複雜度解決方案，用於列印給定字串中相鄰重複字元的頻率。我們將結果儲存在一個配對向量中並打印出來。本文藉助各種示例討論了問題陳述。此外，我們藉助虛擬碼、演算法和實際的 C++ 程式程式碼討論瞭解決方案方法。最後，我們深入討論了時間和空間複雜度，以全面瞭解解決方案。