X
String Compression
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.
Ruby solution:
def compress(chars)
return 0 if chars.empty?
write_index = 0
read_index = 0
while read_index < chars.length
char = chars[read_index]
count = 0
# Count consecutive repeating characters
while read_index < chars.length && chars[read_index] == char
read_index += 1
count += 1
end
# Write the character to the compressed array
chars[write_index] = char
write_index += 1
# If the count is greater than 1, write the count as characters
if count > 1
count.to_s.each_char do |digit|
chars[write_index] = digit
write_index += 1
end
end
end
write_index
end# Example usage:
chars = ["a", "a", "b", "b", "c", "c", "c"]
length = compress(chars)
puts length # Output: 6
puts chars[0, length].inspect # Output: ["a", "2", "b", "2", "c", "3"]In this solution, we see that the function takes an array of characters(`chars`) as input.
It initializes two pointers(`read_index` and `write_index` to iterate through the array.
It iterates through the array, counting consecutive repeating characters and writing the compressed characters to the array in place.
The function returns the length of the compressed array(`write_index`).
The example usage shows how to use the function and retrieve the compressed array and its length.