Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Strings

String Compression

Easy · Strings · Asked at TCS, Infosys, Wipro, Accenture, Cognizant

Compress the string by replacing every run of the same character with the character followed by the run length. Example: aaabcc → a3b1c2.

Input

One string s (lowercase letters).

Output

The compressed string.

Constraints

Example 1

Input

aaabcc

Output

a3b1c2

Example 2

Input

abc

Output

a1b1c1

Hints

  1. Walk the string and find where each run of equal characters ends.
  2. Append the character and the run length. Build the result with a StringBuilder / list — not repeated + on strings.

Approach

Let i be the start of a run and move j forward while s[j] == s[i]. Append s[i] and j − i, then jump i to j. Each character is read once. Use a string builder: repeated + in Java or Python can take O(n²) time.

Complexity: O(n) time · O(n) space for the output

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s, out;
    cin >> s;
    for (size_t i = 0; i < s.size();) {
        size_t j = i;
        while (j < s.size() && s[j] == s[i]) j++;
        out += s[i];
        out += to_string(j - i);
        i = j;
    }
    cout << out << "\n";
    return 0;
}

Python solution

from itertools import groupby

s = input().strip()
print("".join(ch + str(len(list(run))) for ch, run in groupby(s)))

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length();) {
            int j = i;
            while (j < s.length() && s.charAt(j) == s.charAt(i)) j++;
            sb.append(s.charAt(i)).append(j - i);
            i = j;
        }
        System.out.println(sb);
    }
}

Solve String Compression online · All practice problems