String Compression
String Compression is a medium arrays & hashing problem solved with the two pointer pattern.
The best approach, optimal (read and write pointers in place), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from build a new string, then copy back up.
Problem
You are given an array of characters chars. Compress it in place using run-length encoding: every maximal run of equal consecutive characters is replaced by the character itself, followed by the run’s length written in decimal digits. A run of length 1 is written as just the character, with no count. A run of 12 contributes the separate characters '1' and '2'.
Write the compressed result into the beginning of chars and return its length k. Only chars[0..k-1] is checked; whatever remains after it does not matter. Use only constant extra memory.
Examples
Example 1
- Input
chars = ["x", "x", "y", "z", "z", "z"]- Output
5, chars starts with ["x", "2", "y", "z", "3"]- Why
- The runs are xx, y and zzz. A run of length 1 keeps only its character.
Example 2
- Input
chars = ["q"]- Output
1, chars starts with ["q"]- Why
- A single character is already as short as it gets.
Example 3
- Input
chars = ["m", "m", "m", "m", "m", "m", "m", "m", "m", "m", "m", "m", "k"]- Output
4, chars starts with ["m", "1", "2", "k"]- Why
- Twelve m's become m followed by the two digits 1 and 2.
Constraints
1 <= chars.length <= 2000chars[i]is an English letter, a digit or a symbol.- Use only O(1) extra memory.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Build a new string, then copy back | O(n) | O(n) |
| Optimal (read and write pointers in place) | O(n) | O(1) |
1Build a new string, then copy back
O(n)Every character is read once and every output character is written twice.O(n)The builder can hold up to n characters, breaking the O(1) memory rule.Scan the runs and append each run's character and count to a separate string builder. Then copy the builder into the front of the array and return its length.
- i = 0; while i < n: find j, the first index after i whose character differs.
- Append chars[i]; if j - i > 1, append the decimal digits of j - i.
- Set i = j.
- Copy the builder into chars[0..] and return its length.
class Solution {
public int compress(char[] chars) {
StringBuilder sb = new StringBuilder();
int i = 0, n = chars.length;
while (i < n) {
int j = i;
while (j < n && chars[j] == chars[i]) j++;
sb.append(chars[i]);
if (j - i > 1) sb.append(j - i);
i = j;
}
for (int k = 0; k < sb.length(); k++) chars[k] = sb.charAt(k);
return sb.length();
}
}class Solution:
def compress(self, chars: List[str]) -> int:
parts = []
i, n = 0, len(chars)
while i < n:
j = i
while j < n and chars[j] == chars[i]:
j += 1
parts.append(chars[i])
if j - i > 1:
parts.append(str(j - i))
i = j
s = "".join(parts)
for k, c in enumerate(s):
chars[k] = c
return len(s)class Solution {
public:
int compress(vector<char>& chars) {
string sb;
int i = 0, n = chars.size();
while (i < n) {
int j = i;
while (j < n && chars[j] == chars[i]) j++;
sb += chars[i];
if (j - i > 1) sb += to_string(j - i);
i = j;
}
for (int k = 0; k < (int) sb.size(); k++) chars[k] = sb[k];
return sb.size();
}
};function compress(chars) {
let sb = "";
let i = 0;
const n = chars.length;
while (i < n) {
let j = i;
while (j < n && chars[j] === chars[i]) j++;
sb += chars[i];
if (j - i > 1) sb += String(j - i);
i = j;
}
for (let k = 0; k < sb.length; k++) chars[k] = sb[k];
return sb.length;
}2Optimal (read and write pointers in place)
O(n)The read pointer passes each index once; the writes are at most n.O(1)Only a few integer variables; the digits are written straight into the array.Use a read pointer to walk over runs and a write pointer for the compressed output in the same array. The output for a run (1 character plus at most 4 digits) is never longer than the run's own length, so the write pointer never passes the read pointer and nothing unread is overwritten.
- write = 0, read = 0.
- While read < n: c = chars[read]; count the run by advancing read while chars[read] == c.
- chars[write++] = c.
- If the run length is more than 1, write each digit of the length at chars[write++].
- Return write.
class Solution {
public int compress(char[] chars) {
int write = 0, read = 0, n = chars.length;
while (read < n) {
char c = chars[read];
int start = read;
while (read < n && chars[read] == c) read++;
chars[write++] = c;
int len = read - start;
if (len > 1) {
for (char d : Integer.toString(len).toCharArray()) {
chars[write++] = d;
}
}
}
return write;
}
}class Solution:
def compress(self, chars: List[str]) -> int:
write = read = 0
n = len(chars)
while read < n:
c = chars[read]
start = read
while read < n and chars[read] == c:
read += 1
chars[write] = c
write += 1
length = read - start
if length > 1:
for d in str(length):
chars[write] = d
write += 1
return writeclass Solution {
public:
int compress(vector<char>& chars) {
int write = 0, read = 0, n = chars.size();
while (read < n) {
char c = chars[read];
int start = read;
while (read < n && chars[read] == c) read++;
chars[write++] = c;
int len = read - start;
if (len > 1) {
for (char d : to_string(len)) {
chars[write++] = d;
}
}
}
return write;
}
};function compress(chars) {
let write = 0, read = 0;
const n = chars.length;
while (read < n) {
const c = chars[read];
const start = read;
while (read < n && chars[read] === c) read++;
chars[write++] = c;
const len = read - start;
if (len > 1) {
for (const d of String(len)) {
chars[write++] = d;
}
}
}
return write;
}Edge cases to test
- A single character
- No repeated characters at all: nothing changes and the length stays n
- A run of 10 or more: its count takes several characters
- The same character in two separate runs, like a a b a, is compressed run by run
Hints
Hint 1
Process the array run by run: find where the current run of equal characters ends.
Hint 2
The compressed text is never longer than the part of the array you have already read, so you can write it into the same array.
Hint 3
Keep a read pointer and a write pointer. For each run write the character, then (if the run is longer than 1) the digits of its length.
FAQ
What is the best time complexity for String Compression?
Optimal (read and write pointers in place) runs in O(n) time and O(1) extra space. The read pointer passes each index once; the writes are at most n.
Which pattern does String Compression use?
It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.
Is there a brute force solution for String Compression?
Yes. Build a new string, then copy back takes O(n) time and O(n) space. Scan the runs and append each run's character and count to a separate string builder.
Which edge cases should I test for String Compression?
A single character; No repeated characters at all: nothing changes and the length stays n; A run of 10 or more: its count takes several characters; The same character in two separate runs, like a a b a, is compressed run by run.