Given an array of characters chars
, compress it using the following algorithm:
Begin with an empty string s
. For each group of consecutive repeating characters in chars
:
- If the group's length is 1, append the character to
s
. - Otherwise, append the character followed by the group's length.
The compressed string s
should not be returned separately, but instead be stored in the input character array chars
. Note that group lengths that are 10 or longer will be split into multiple characters in chars
.
After you are done modifying the input array, return the new length of the array.
You must write an algorithm that uses only constant extra space.
Example 1:
Input: chars = ["a","a","b","b","c","c","c"] Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"] Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".
Example 2:
Input: chars = ["a"] Output: Return 1, and the first character of the input array should be: ["a"] Explanation: The only group is "a", which remains uncompressed since it's a single character.
Example 3:
Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"] Output: Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"]. Explanation: The groups are "a" and "bbbbbbbbbbbb". This compresses to "ab12".
Example 4:
Input: chars = ["a","a","a","b","b","a","a"] Output: Return 6, and the first 6 characters of the input array should be: ["a","3","b","2","a","2"]. Explanation: The groups are "aaa", "bb", and "aa". This compresses to "a3b2a2". Note that each group is independent even if two groups have the same character.
Constraints:
1 <= chars.length <= 2000
chars[i]
is a lower-case English letter, upper-case English letter, digit, or symbol.
Companies:
Goldman Sachs, Microsoft, Apple, Facebook, Amazon, Yandex, Google, Cisco, eBay, Redfin, Nvidia
Related Topics:
String
Similar Questions:
- Count and Say (Medium)
- Encode and Decode Strings (Medium)
- Design Compressed String Iterator (Easy)
- Decompress Run-Length Encoded List (Easy)
// OJ: https://leetcode.com/problems/string-compression/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(log_10^N)
class Solution {
public:
int compress(vector<char>& A) {
int j = 0;
for (int i = 0; i < A.size(); ++i) {
char c = A[i];
int cnt = 1;
while (i + 1 < A.size() && A[i + 1] == c) ++i, ++cnt;
A[j++] = c;
if (cnt == 1) continue;
auto s = to_string(cnt);
for (char d : s) A[j++] = d;
}
return j;
}
};
Or don't use to_string
which takes extra space.
// OJ: https://leetcode.com/problems/string-compression/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
int compress(vector<char>& A) {
int j = 0;
for (int i = 0; i < A.size(); ++i) {
char c = A[i];
int cnt = 1, p = 1;
while (i + 1 < A.size() && A[i + 1] == c) ++i, ++cnt;
A[j++] = c;
if (cnt == 1) continue;
while (cnt / p) p *= 10;
for (p /= 10; p; p /= 10) {
A[j++] = '0' + cnt / p;
cnt %= p;
}
}
return j;
}
};