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[0]
# 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 resvar compress = function(chars) {
// keep track of the current character we are on
let current = chars[0];
// 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[0];
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;
}
}