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 sshould 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.
Problem Statement
The problem requires us to compress a given array of characters 'chars' using a specific algorithm, such that consecutive repeating characters are
represented by the character followed by its count. If a group of characters is not repeated, it should simply be represented by the character
itself. The compressed string should be stored in the input character array 'chars' and the function should return the new length of the array
after modification. The compressed string should not be returned separately, and the algorithm must use only constant extra space. Group lengths
that are 10 or longer will be split into multiple characters in 'chars'.
Examples
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".
Clarifying Questions
What is the size range of the input array 'chars'?
Can we assume that the input array 'chars' contains only uppercase and lowercase English letters?
Should the function modify the original input array or create a new one?
Is it acceptable to modify the input array in place, including removing elements?
Can we assume that the input array 'chars' is not null or empty?
Is it required to return the compressed string s, or just the new length of the array?
Is it necessary to preserve the order of characters in the compressed string?
Can we use any built-in functions or libraries in our solution?
String Compression Solutions
There are different approaches to solving this problem. Some of them include:
Two-pointers
String Concatenation
Stack
Two-pointers Approach:
This approach involves iterating through the array and keeping track of the current character and its count. Whenever the current character
changes, we append the compressed characters to the output string and reset the count.
Algorithm:
Initialize variables currentChar and count to the first character in the array and 1, respectively.
Iterate through the array from the second character.
If the current character is the same as the previous character, increment the count.
If the current character is different from the previous character, append the previous character to the output string, followed by its count if
the count is greater than 1.
Update currentChar to the current character and reset the count to 1.
After the loop, append the last character to the output string, followed by its count if the count is greater than 1.
public class Solution {
public int Compress(char[] chars) {
int i = 0; // Initialize pointer i to the beginning of the array
int j = 0; // Initialize pointer j to the beginning of the array
while (j < chars.Length) { // Iterate through the array using pointer j
int count = 1; // Initialize count to 1
while (j + 1 < chars.Length && chars[j] == chars[j + 1]) { // While the next character is the same as the current character and we have not reached the end of the array
count++; // Increment the count
j++; // Move pointer j to the next character
}
chars[i++] = chars[j]; // Append the current character to the output array
if (count > 1) { // If the count is greater than 1
foreach (char c in count.ToString()) { // Convert the count to a string and iterate through each character
chars[i++] = c; // Append the current digit to the output array
}
}
j++; // Move pointer j to the next character
}
return i; // Return the new length of the array
}
}
class Solution:
def compress(self, chars: List[str]) -> int:
i = 0 # Initialize pointer i to the beginning of the array
j = 0 # Initialize pointer j to the beginning of the array
while j < len(chars): # Iterate through the array using pointer j
count = 1 # Initialize count to 1
while j + 1 < len(chars) and chars[j] == chars[j + 1]: # While the next character is the same as the current character and we have not reached the end of the array
count += 1 # Increment the count
j += 1 # Move pointer j to the next character
chars[i] = chars[j] # Append the current character to the output array
i += 1
if count > 1: # If the count is greater than 1
for c in str(count): # Convert the count to a string and iterate through each character
chars[i] = c # Append the current digit to the output array
i += 1
j += 1 # Move pointer j to the next character
return i # Return the new length of the array
class Solution {
public int compress(char[] chars) {
int i = 0; // Initialize pointer i to the beginning of the array
int j = 0; // Initialize pointer j to the beginning of the array
while (j < chars.length) { // Iterate through the array using pointer j
int count = 1; // Initialize count to 1
while (j + 1 < chars.length && chars[j] == chars[j + 1]) { // While the next character is the same as the current character and we have not reached the end of the array
count++; // Increment the count
j++; // Move pointer j to the next character
}
chars[i] = chars[j]; // Append the current character to the output array
i++;
if (count > 1) { // If the count is greater than 1
for (char c : String.valueOf(count).toCharArray()) { // Convert the count to a string and iterate through each character
chars[i] = c; // Append the current digit to the output array
i++;
}
}
j++; // Move pointer j to the next character
}
return i; // Return the new length of the array
}
}
class Solution {
public:
int compress(vector<int>& chars) {
int i = 0; // Initialize pointer i to the beginning of the array
int j = 0; // Initialize pointer j to the beginning of the array
while (j < chars.size()) { // Iterate through the array using pointer j
int count = 1; // Initialize count to 1
while (j + 1 < chars.size() && chars[j] == chars[j + 1]) { // While the next character is the same as the current character and we have not reached the end of the array
count++; // Increment the count
j++; // Move pointer j to the next character
}
chars[i] = chars[j]; // Append the current character to the output array
i++;
if (count > 1) { // If the count is greater than 1
string count_str = to_string(count); // Convert the count to a string
for (char c : count_str) { // Iterate through each character in the string
chars[i] = c; // Append the current digit to the output array
i++;
}
}
j++; // Move pointer j to the next character
}
return i; // Return the new length of the array
}
};
Time complexity: O(n), where n is the length of the input array. This is because we only iterate over the array once.
Space complexity: O(1), since we only use constant extra space.
Using Stack Approach:
This approach involves using a stack to keep track of the current group of repeating characters. We can then iterate through the array, push the
current character onto the stack if it matches the top element, and pop the stack if it doesn't match. Whenever we pop the stack, we append the
compressed characters to the output string.
Algorithm:
Initialize an empty stack and push the first character in the array onto the stack.
Iterate through the array from the second character.
If the current character is the same as the top element of the stack, push the current character onto the stack.
If the current character is different from the top element of the stack, pop the stack and append the popped character to the output string,
followed by its count if the count is greater than 1.
Repeat steps 3-4 until the stack is empty or the current character is successfully pushed onto the stack.
After the loop, pop any remaining characters from the stack and append them to the output string, followed by their counts if the counts are
greater than 1.
public class Solution {
public int Compress(char[] chars) {
Stack<(char, int)> stack = new Stack<(char, int)>(); // Initialize a stack to hold pairs of characters and their counts
foreach (char c in chars) { // Iterate through the characters in the input array
if (!stack.TryPeek(out var top) || top.Item1 != c) { // If the stack is empty or the top element is not the same as the current character
stack.Push((c, 1)); // Push a new pair onto the stack with count 1
} else { // If the top element is the same as the current character
stack.Pop();
stack.Push((c, top.Item2 + 1)); // Increment the count of the top element
}
}
int i = 0; // Initialize pointer i to the beginning of the array
while (stack.Count > 0) { // While the stack is not empty
var (c, count) = stack.Pop(); // Get the top pair from the stack
chars[i] = c; // Append the character to the output array
i++;
if (count > 1) { // If the count is greater than 1
string count_str = count.ToString(); // Convert the count to a string
foreach (char ch in count_str) { // Iterate through each character in the string
chars[i] = ch; // Append the current digit to the output array
i++;
}
}
}
Array.Reverse(chars, 0, i); // Reverse the output array
return i; // Return the new length of the array
}
}
class Solution:
def compress(self, chars: List[str]) -> int:
stack = [] # Initialize a stack to hold pairs of characters and their counts
for c in chars: # Iterate through the characters in the input array
if not stack or stack[-1][0] != c: # If the stack is empty or the top element is not the same as the current character
stack.append([c, 1]) # Push a new pair onto the stack with count 1
else: # If the top element is the same as the current character
stack[-1][1] += 1 # Increment the count of the top element
i = 0 # Initialize pointer i to the beginning of the array
while stack: # While the stack is not empty
c, count = stack.pop() # Get the top pair from the stack
chars[i] = c # Append the character to the output array
i += 1
if count > 1: # If the count is greater than 1
count_str = str(count) # Convert the count to a string
for c in count_str: # Iterate through each character in the string
chars[i] = c # Append the current digit to the output array
i += 1
chars[:i] = reversed(chars[:i]) # Reverse the output array
return i # Return the new length of the array
class Solution {
public int compress(char[] chars) {
Stack<Pair<Character, Integer>> st = new Stack<>(); // Initialize a stack to hold pairs of characters and their counts
for (char c : chars) { // Iterate through the characters in the input array
if (st.isEmpty() || !st.peek().getKey().equals(c)) { // If the stack is empty or the top element is not the same as the current character
st.push(new Pair<>(c, 1)); // Push a new pair onto the stack with count 1
} else { // If the top element is the same as the current character
st.peek().setValue(st.peek().getValue() + 1); // Increment the count of the top element
}
}
int i = 0; // Initialize pointer i to the beginning of the array
while (!st.isEmpty()) { // While the stack is not empty
Pair<Character, Integer> p = st.pop(); // Get the top pair from the stack
chars[i] = p.getKey(); // Append the character to the output array
i++;
if (p.getValue() > 1) { // If the count is greater than 1
String count_str = Integer.toString(p.getValue()); // Convert the count to a string
for (char c : count_str.toCharArray()) { // Iterate through each character in the string
chars[i] = c; // Append the current digit to the output array
i++;
}
}
}
reverse(chars, 0, i); // Reverse the output array
return i; // Return the new length of the array
}
}
class Solution {
public:
int compress(vector<int>& chars) {
stack<pair<char, int>> st; // Initialize a stack to hold pairs of characters and their counts
for (char c : chars) { // Iterate through the characters in the input array
if (st.empty() || st.top().first != c) { // If the stack is empty or the top element is not the same as the current character
st.push(make_pair(c, 1)); // Push a new pair onto the stack with count 1
} else { // If the top element is the same as the current character
st.top().second++; // Increment the count of the top element
}
}
int i = 0; // Initialize pointer i to the beginning of the array
while (!st.empty()) { // While the stack is not empty
pair<char, int> p = st.top(); // Get the top pair from the stack
st.pop(); // Pop the top pair from the stack
chars[i] = p.first; // Append the character to the output array
i++;
if (p.second > 1) { // If the count is greater than 1
string count_str = to_string(p.second); // Convert the count to a string
for (char c : count_str) { // Iterate through each character in the string
chars[i] = c; // Append the current digit to the output array
i++;
}
}
}
reverse(chars.begin(), chars.begin() + i); // Reverse the output array
return i; // Return the new length of the array
}
};
Time complexity: O(n), where n is the length of the input array. This is because we only iterate over the array once and
perform constant time operations on the stack.
Space complexity: O(n), since we use a stack to store the characters and their counts. In the worst case, when all
characters are unique, the stack will contain n elements.
String Concatenation Approach:
This approach involves concatenating the compressed characters directly to the output string instead of appending them to an intermediate data
structure. We can then iterate through the array and update the output string accordingly.
Algorithm:
Initialize an empty output string and variables currentChar and count to the first character in the array and 1, respectively.
Iterate through the array from the second character.
If the current character is the same as the previous character, increment the count.
If the current character is different from the previous character, append the previous character to the output string, followed by its count if
the count is greater than 1.
Update currentChar to the current character and reset the count to 1.
After the loop, append the last character to the output string, followed by its count if the count is greater than 1.
public class Solution {
public int Compress(char[] chars) {
// check if the array is null or empty
if (chars == null || chars.Length == 0) {
return 0;
}
// initialize variables
char prev = chars[0]; // previous character
int count = 1; // count of consecutive characters
string result = ""; // compressed string
// loop through the array
for (int i = 1; i < chars.Length; i++) {
// if current character is the same as previous character
if (chars[i] == prev) {
count++; // increment count
} else { // if current character is different from previous character
// append previous character to result string
result += prev;
// if count is greater than 1, append count as string to result string
if (count > 1) {
result += count.ToString();
}
// update previous character and reset count
prev = chars[i];
count = 1;
}
}
// append last character and count to result string
result += prev;
if (count > 1) {
result += count.ToString();
}
// copy result string to original char array and return length of compressed array
char[] res = result.ToCharArray();
Array.Copy(res, chars, res.Length);
return res.Length;
}
}
class Solution:
def compress(self, chars: List[str]) -> int:
if not chars: # If the input array is empty
return 0
curr_char = chars[0] # Initialize the current character to the first element of the array
count = 1 # Initialize the count to 1
output = curr_char # Initialize the output string with the first character
for c in chars[1:]: # Iterate through the remaining characters in the array
if c != curr_char: # If the current character is different from the previous character
if count > 1: # If the count is greater than 1
output += str(count) # Append the count to the output string
curr_char = c # Update the current character to the current element
output += curr_char # Append the current character to the output string
count = 1 # Reset the count to 1
else: # If the current character is the same as the previous character
count += 1 # Increment the count
if count > 1: # If the last group of consecutive characters has a count greater than 1
output += str(count) # Append the count to the output string
for i, c in enumerate(output): # Iterate through the characters in the output string
chars[i] = c # Update the input array with the compressed characters
return len(output) # Return the length of the output string
import java.util.*;
class Solution {
public int compress(char[] chars) {
if (chars == null || chars.length == 0) { // If the input array is null or empty
return 0;
}
char curr_char = chars[0]; // Initialize the current character to the first element of the array
int count = 1; // Initialize the count to 1
StringBuilder sb = new StringBuilder(); // Initialize a StringBuilder to store the compressed string
sb.append(curr_char); // Append the first character to the StringBuilder
for (int i = 1; i < chars.length; i++) { // Iterate through the remaining characters in the array
char c = chars[i];
if (c != curr_char) { // If the current character is different from the previous character
if (count > 1) { // If the count is greater than 1
sb.append(count); // Append the count to the StringBuilder
}
curr_char = c; // Update the current character to the current element
sb.append(curr_char); // Append the current character to the StringBuilder
count = 1; // Reset the count to 1
} else { // If the current character is the same as the previous character
count++; // Increment the count
}
}
if (count > 1) { // If the last group of consecutive characters has a count greater than 1
sb.append(count); // Append the count to the StringBuilder
}
String output = sb.toString(); // Convert the StringBuilder to a string
for (int i = 0; i < output.length(); i++) { // Iterate through the characters in the output string
chars[i] = output.charAt(i); // Update the input array with the compressed characters
}
return output.length(); // Return the length of the output string
}
}
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int compress(vector<int>& chars) {
// Initialize an empty string to store the compressed characters
string s = "";
// Initialize a counter to count the consecutive characters
int count = 1;
// Get the length of the input array
int n = chars.size();
// Iterate over the array of characters
for(int i = 1; i <= n; i++) {
// Check if the current character is the same as the previous character
if(i < n && chars[i] == chars[i-1]) {
// If yes, increment the counter
count++;
} else {
// If no, add the previous character to the compressed string
s += chars[i-1];
// If the count is greater than 1, add the count to the compressed string
if(count > 1) {
s += to_string(count);
// Reset the count to 1
count = 1;
}
}
}
// Convert the compressed string to a vector of characters and update the input array
chars = vector<char>(s.begin(), s.end());
// Return the length of the compressed string
return s.length();
}
Time complexity: O(n), where n is the length of the input array. This is because we only iterate over the array once and
perform constant time operations on the string.
Space complexity: O(n), since we use a string to store the compressed characters. In the worst case, when all characters are
unique, the string will contain n elements.
In terms of time and space complexity, the Two-Pointer Approach is the most optimal. The approache have a time complexity of O(n) and a space
complexity of O(1), which means they can solve the problem efficiently without using much additional space.
The Stack Approach and String Concatenation Approach have higher space complexities, which can be a problem for larger input arrays. Therefore,
they may not be as optimal as the Two-Pointer and Iterative approaches, especially for very large input arrays.
Overall, the Two-Pointer Approach and Iterative Approach are the most optimal for solving this problem.
