ゆめさくエンジニア研究所
文字列問題 02

続く​同じ​文字を​数で縮める

続く​同じ​文字を​「文字と​続いた​数」に​縮め、​短くなった​ときだけ​縮めた方を​返す。​同じ​文字の​ひと​続きを​数えながら、​結果を​少しずつ組み立てる​練習です。

問題

英小文字だけでできた文字列 s を受け取ります。同じ文字が続くところを、その文字と続いた数に置き換えて縮めます。たとえば aaabcc は a3b1c2 になります。1 回しか出ない文字にも、数の 1 を付けます。

  • 縮めた文字列が元の s より短くなるときだけ、縮めた方を返します
  • 縮めた方が元と同じ長さか、元より長くなるときは、元の s をそのまま返します
  • s が空の文字列なら、空の文字列を返します
  • s の長さは 0 以上 10000 以下です

入力と出力の例

例 1

縮めると 9 文字が 6 文字になるので、縮めた方を返します。

入力

s = "aaaabbbcc"

出力

"a4b3c2"

例 2

縮めた a3b1c2 は 6 文字で、元と同じ長さです。短くならないので、元のまま返します。

入力

s = "aaabcc"

出力

"aaabcc"

例 3

続いた数が 2 桁になることもあります。

入力

s = "zzzzzzzzzzzz"

出力

"z12"

面接での聞かれ方

面接では、例を 1 つ見せて口で説明されることが多いです。

  • 「aaabcc を a3b1c2 のように縮める関数を書いてください」
  • 「縮めても短くならないときはどうしますか？」と、返す物の決まりをあとから足されます
  • 書き終えたあとに「文字列を足していく書き方の計算量は？」と聞かれることもあります

数が 2 桁以上になってもよいのか、1 回だけの文字にも 1 を付けるのかを、最初に確かめておきます。ここを決めないまま書くと、あとで直す所が増えます。

まず考える手順

段 1

まずは、続く同じ文字のひと続きを見つけることを考えます。位置 i の文字から始めて、同じ文字が続くかぎり位置 j を進めます。j が止まったところで、i から j の手前までが 1 つのひと続きで、その長さは j - i です。

段 2

ひと続きを 1 つ見つけるたびに、文字と長さを結果に書き足し、i を j に進めます。結果を文字列に += で足していく書き方でも動きます。ただ、言語によっては足すたびに文字列を作り直すので、長い入力で遅くなることがあります。

段 3

そこで、書き足す物はいったん並びにためておき、最後に 1 回だけつなぎます。つないだ文字列の長さを元の s と比べ、短いときだけ縮めた方を返します。空の文字列は繰り返しに入らず、縮めた方も空になるので、比べると元の空の文字列が返ります。

ここから​解答です。​先に​自分で​書いてから​読むと、​考え方が​残ります。

解答

Python

Python

def compress_runs(s):
    parts = []
    i = 0
    n = len(s)
    while i < n:
        j = i
        while j < n:
            if s[j] != s[i]:
                break
            j += 1
        text = s[i] + str(j - i)
        parts.append(text)
        i = j
    out = "".join(parts)
    if len(out) < n:
        return out
    return s

JavaScript

JavaScript

function compressRuns(s) {
  const parts = [];
  const n = s.length;
  let i = 0;
  while (i < n) {
    let j = i;
    while (j < n) {
      if (s[j] !== s[i]) {
        break;
      }
      j++;
    }
    const k = j - i;
    parts.push(s[i] + k);
    i = j;
  }
  const out = parts.join("");
  if (out.length < n) {
    return out;
  }
  return s;
}

比べる式は「より短い」です。「以下」にすると、例 2 のように同じ長さのときに縮めた方を返してしまいます。

計算量

  • 時間は O(n) です。i と j はどちらも前にしか進まないので、どの文字も一定の回数しか読みません
  • 使う記憶は O(n) です。縮めた結果は、最悪の場合に元の 2 倍の長さになります
  • 段 2 の、文字列に足していく書き方は、言語によっては時間が O(n²) まで落ちます

よくある間違い

  • 最後のひと続きを書き足し忘れる。「前の文字と違ったら書き足す」書き方にすると、文字列の終わりに来たときの分が抜けます。例 1 なら c2 が付かずに a4b3 を返します
  • 数を 1 桁と決めつける。長さを文字 1 つで書こうとすると、例 3 の 12 が正しく書けません。数は文字列にしてからつなぎます
  • 比べる式を「以下」にする。同じ長さのときは元を返す決まりなので、「より短い」で比べます

面接での話し方の例

書き始める前に、方針を短く口に出します。

「前から読んで、同じ文字が続くひと続きを 2 つの位置で見つけます。見つけるたびに文字と長さを並びにためて、最後に 1 回だけつなぎます。つないだ物が元より短いときだけそれを返し、そうでなければ元を返します。時間も記憶も O(n) です。」

書き終えたら、例を 1 つ手でたどって見せます。

「例 2 の "aaabcc" でたどります。a が 3 つ、b が 1 つ、c が 2 つなので、つなぐと a3b1c2 の 6 文字です。元も 6 文字で短くなっていないので、元の aaabcc を返します。」

解答を動かした版 Python 3.12.14Node.js 22.23.4確認日 2026年10月24日

コーディング面接問題の一覧へ戻る