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
- 1 ≤ |s| ≤ 10^5
Example 1
Input
aaabcc
Output
a3b1c2
Example 2
Input
abc
Output
a1b1c1
Hints
- Walk the string and find where each run of equal characters ends.
- 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);
}
}