# Solution For String Compression

Problem Statement:

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 have adjacent repeating characters. Return the compressed string.

Solution:

The problem can be solved by iterating through the given array of chars and keeping track of the current character and its count. Whenever a new character is encountered, the count of the previous character is appended to the resulting string s along with the character itself. The count is set to 1 for the new character. If a character is encountered again, the count is incremented. After the loop is complete, the last character’s count is appended to the resulting string.

Algorithm:

• Initialize an empty string s and set the count variable to 1.
• Iterate through the characters of the given array, starting from the second character.
• If the current character is the same as the previous character, increment count.
• If the current character is different from the previous character, append the previous character and its count to s and set the count variable to 1.
• After the loop, append the last character and its count to s.
• Return the resulting string s.

Pseudo Code:

s = “”
count = 1
for i in range(1, len(chars)):
if chars[i] == chars[i-1]:
count += 1
else:
s += chars[i-1] + str(count)
count = 1
s += chars[-1] + str(count)
return s

Time Complexity:

The time complexity of the solution is O(n) as we are iterating through each character of the given array once.

Space Complexity:

The space complexity of the solution is O(1) as we are not using any extra space apart from the resulting string s and the count variable.

Code:

class Solution:
def compress(self, chars: List[str]) -> int:
s = “”
count = 1
for i in range(1, len(chars)):
if chars[i] == chars[i-1]:
count += 1
else:
s += chars[i-1] + str(count)
count = 1
s += chars[-1] + str(count)
chars[:] = list(s)
return len(chars)

## Step by Step Implementation For String Compression

```public class Solution {
public int compress(char[] chars) {
int indexAns = 0, index = 0;
while(index < chars.length){
char currentChar = chars[index];
int count = 0;
while(index < chars.length && chars[index] == currentChar){
index++;
count++;
}
chars[indexAns++] = currentChar;
if(count != 1)
for(char c : Integer.toString(count).toCharArray())
chars[indexAns++] = c;
}
return indexAns;
}
}```
```def stringCompression(s):

# Base case
if len(s) == 0:
return ""

# Initialize result
res = ""

# First character
res += s

# Initialize count of matching characters
count = 1

# Loop through characters of the string
for i in range(1, len(s)):

# If the current character matches with the next
if s[i] == s[i - 1]:
count += 1

# If doesn't match, update result
else:
if count > 1:
res += str(count)
res += s[i]
count = 1

# If some character left
if count > 1:
res += str(count)

return res```
```var compress = function(chars) {
// keep track of the current character we are on
let current = chars;
// keep track of the count of the current character
let count = 1;
// start from the second character
for (let i = 1; i <= chars.length; i++) {
// if the current character is the same as the next character
if (chars[i] === current) {
// increment the count
count++;
} else {
// otherwise, we have reached the end of the current character
// so we set the character at the current index to the current character
chars[i - 1] = current;
// if the count is greater than 1, we need to add the count to the array
if (count > 1) {
// convert the count to a string
count = count.toString();
// then add each character of the count to the array
for (let j = 0; j < count.length; j++) {
chars[i + j] = count[j];
}
// increment i by the length of the count - 1 to account for the characters we added
i += count.length - 1;
}
// reset the current character and count
current = chars[i];
count = 1;
}
}
// return the first i characters, which will be the compressed array
return chars.slice(0, i);
};```
```class Solution {
public:
int compress(vector& chars) {
int n = chars.size();
if(n == 0) return 0;
int i = 0, j = 0, count = 1;
while(j < n){
if(j == n-1 || chars[j] != chars[j+1]){
chars[i++] = chars[j];
if(count > 1){
string s = to_string(count);
for(char c : s) chars[i++] = c;
}
count = 1;
}
else count++;
j++;
}
return i;
}
};```
```public class Solution {
public int Compress(char[] chars) {
// check for edge cases
if (chars == null || chars.Length == 0) {
return 0;
}

int slow = 0;
int fast = 0;
int count = 0;

// keep track of the last character we saw
char lastChar = chars;

while (fast < chars.Length) {
// if the current character is the same as the last one, increment the count
if (chars[fast] == lastChar) {
count++;
}
// otherwise, we need to compress the characters we've seen so far
else {
// first, write the character to the array
chars[slow] = lastChar;
slow++;

// next, check if the count is greater than 1. If so, we need to write the count to the array as well
if (count > 1) {
// convert the count to a string
string countStr = count.ToString();

// write each character of the string to the array
for (int i = 0; i < countStr.Length; i++) {
chars[slow] = countStr[i];
slow++;
}
}

// finally, update the last character we saw and reset the count
lastChar = chars[fast];
count = 1;
}

fast++;
}

// don't forget to compress the last set of characters!
chars[slow] = lastChar;
slow++;

if (count > 1) {
string countStr = count.ToString();

for (int i = 0; i < countStr.Length; i++) {
chars[slow] = countStr[i];
slow++;
}
}

return slow;
}
}```

Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]