打印给定字符串中相邻重复字符的频率

---

字符串是一种数据结构，由一系列字符组成。字符串的结尾用一个特殊的字符标记，称为空字符，通常用 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++ 程序代码讨论了解决方案方法。最后，我们深入讨论了时间和空间复杂度，以全面了解解决方案。