C++で文字列を圧縮する方法：連続する重複文字を1つにまとめる

はじめに

文字列 s が与えられたとき、連続して重複している文字を取り除き、各文字を1つだけ残した新しい文字列を返すことを考えます。同じ文字が続けて現れる場合は、それらを1文字にまとめます。文字の出現順序は元のまま維持されます。

例として、入力が "heeeeelllllllloooooo" の場合、出力は "helo" になります。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• 結果を格納するための空の文字列 ret を用意します。
• i = 0 から s のサイズ未満まで、i を1ずつ増やしながらループします。
• ret が空でなく、ret の最後の文字が s[i] と同じである場合は、その文字をスキップして次の反復へ進みます。
• それ以外の場合は、s[i] を ret の末尾に連結します。
• ループ終了後、ret を返します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
  public:
  string solve(string s) {
    string ret = "";
    for(int i = 0; i < s.size(); i++){
      if(ret.size() && ret.back() == s[i]){
        continue;
      }
      ret += s[i];
    }
    return ret;
  }
};
int main(){
  Solution ob;
  cout << (ob.solve("heeeeelllllllloooooo"));
}

入力

"heeeeelllllllloooooo"

出力

helo

コードの解説

このアルゴリズムのポイントは、std::string::back() メソッドを使って、結果文字列の末尾の文字と現在処理中の文字を比較する点です。両者が一致する場合は continue によってその文字をスキップし、一致しない場合のみ文字を追加します。これにより、連続する重複文字が自然に1文字へと圧縮されます。

計算量について見てみましょう。入力文字列を一度だけ走査するため、時間計算量は O(n) です。また、結果を格納する文字列が必要となるため、空間計算量も O(n) となります（n は入力文字列の長さ）。

なお、C++20以降では std::ranges::unique や std::unique を活用することでも同様の処理を実現できますが、この手動実装のアプローチはロジックが明快で、学習目的にも非常に適しています。