Every day a Leetcode

题目来源：面试题 01.06. 字符串压缩

解法1：分组循环

分组循环统计连续字符的出现次数，构造压缩字符串，比较原字符串和压缩字符串的长度，返回长度较小的那个。

代码：

class Solution {
public:string compressString(string S) {int n = S.length();vector<pair<char, int>> cnt;// 分组循环int i = 0;while (i < n) {int j = i;while (j < n && S[i] == S[j])j++;cnt.push_back(make_pair(S[i], j - i));i = j;}string Sc;for (auto& p : cnt) {Sc.push_back(p.first);Sc += to_string(p.second);}if (Sc.length() < n)return Sc;return S;}
};

结果：

复杂度分析：

时间复杂度：O(n)，其中 n 是字符串 S 的长度。

空间复杂度：O(n)，其中 n 是字符串 S 的长度。