Dare2Solve
The problem is to compress a list of characters by converting consecutive duplicate characters into the character followed by the number of occurrences. The compressed list must be stored in-place, and the function should return the new length of the list after compression. If a character appears only once, it is simply kept without appending any count.
The intuition behind this problem is that we can iterate through the list and count the occurrences of each character. As we move through the list, we can replace the characters in-place with the compressed format (character + count) if the count is greater than 1. This allows us to compress the string while keeping the space complexity minimal.
i
for placing the compressed characters in the list and j
for iterating through the list.i
position in the list with the current character.i
accordingly.i
at the end.The time complexity is (O(n)), where (n) is the length of the list. This is because we traverse the list once and perform a constant amount of work for each character.
The space complexity is (O(1)) because we modify the list in place and do not use any extra space proportional to the input size.
class Solution {
public:
int compress(vector<char>& chars) {
int i = 0;
int j = 0;
while (j < chars.size()) {
int count = 0;
char curr = chars[j];
while (j < chars.size() && chars[j] == curr) {
j++;
count++;
}
chars[i++] = curr;
if (count > 1) {
for (char digit : to_string(count)) {
chars[i++] = digit;
}
}
}
return i;
}
};
class Solution:
def compress(self, chars: List[str]) -> int:
i = 0
j = 0
while j < len(chars):
count = 0
curr = chars[j]
while j < len(chars) and chars[j] == curr:
j += 1
count += 1
chars[i] = curr
i += 1
if count > 1:
for digit in str(count):
chars[i] = digit
i += 1
return i
class Solution {
public int compress(char[] chars) {
int i = 0;
int j = 0;
while (j < chars.length) {
int count = 0;
char curr = chars[j];
while (j < chars.length && chars[j] == curr) {
j++;
count++;
}
chars[i++] = curr;
if (count > 1) {
for (char digit : Integer.toString(count).toCharArray()) {
chars[i++] = digit;
}
}
}
return i;
}
}
var compress = function (chars) {
let i = 0;
let j = 0;
while (j < chars.length) {
let count = 0;
let curr = chars[j];
while (j < chars.length && chars[j] === curr) {
j++;
count++;
}
chars[i++] = curr;
if (count > 1) {
for (let digit of count.toString()) {
chars[i++] = digit;
}
}
}
return i;
};