String Compression

class Solution {
public:
    int modifyString(vector<char>& input) {
        int index = 0, updatedIndex = 0;
        while (index < input.size()) {
            int length = 1;
            while (index + length < input.size() && input[index + length] == input[index]) {
                length++;
            }
            input[updatedIndex++] = input[index];
            if (length > 1) {
                for (char digit : to_string(length)) {
                    input[updatedIndex++] = digit;
                }
            }
            index += length;
        }
        return updatedIndex;
    }
};

Solution Summary: String Compression in C++

In this string compression task, the goal is to compress a sequence of characters by reducing sequences of the same character to the character followed by the count of repetitions if it is greater than one. The implementation employs a simple while loop strategy to iterate over the input characters and compress them in place, making the process efficient and quick.

• Start by initializing two indices, index used for reading the original characters and updatedIndex used for writing the compressed characters.
• Use a while loop to check each character in the input vector.
• For each character, initialize a length variable to keep track of how many times the character is consecutively repeated.
• Inner loop checks for repeating characters and increments the length.
• Place the character being processed at the updatedIndex position. Increment updatedIndex.
• If the length of repetition is greater than one (i.e., the character is repeated), convert the length to a string and loop through each digit, placing each digit into the input vector at the updated index.
• Increment both index by the length (to move to the next new character) and updatedIndex as required after inserting characters or lengths.
• After processing all characters, return updatedIndex, which is the new length of the compressed character array.

This approach modifies the input vector in place, eliminating the need for extra space (beyond minimal use for the length-to-string conversion), making it efficient in terms of both time and space.

class Solution {
    public int compressChars(char[] chars) {
        int index = 0, resultPos = 0;
        while (index < chars.length) {
            int count = 1;
            while (index + count < chars.length && chars[index + count] == chars[index]) {
                count++;
            }
            chars[resultPos++] = chars[index];
            if (count > 1) {
                for (char digit : Integer.toString(count).toCharArray()) {
                    chars[resultPos++] = digit;
                }
            }
            index += count;
        }
        return resultPos;
    }
}

This Java solution compresses strings by grouping consecutive identical characters in an array and replacing them with the character followed by its count. This approach uses in-place modification for efficiency.

• Start by initializing index to 0 to iterate through the input character array, and resultPos to 0 to track the position in the array where the compressed characters should be inserted.
• Iterate over the array using a while loop until index is less than the length of the character array.
• For each character at the current index, count consecutive duplicates by initializing a count variable and using a nested while loop. This nested loop increments count as long as the next character is the same as the current.
• Place the character into the array at the current resultPos, then increment resultPos.
• If count is greater than one, convert count to its character array and append each digit to chars at subsequent resultPos, and then increment resultPos accordingly.
• Increment index by count to skip the compressed characters.
• Return resultPos, which represents the length of the compressed array.

This method efficiently compresses the array without needing additional space, thereby modifying the original array directly based on the count of consecutive identical characters.

class Solution:
    def compress_string(self, characters: List[str]) -> int:
        index = 0
        output_pos = 0
        while index < len(characters):
            count = 1
            while (index + count < len(characters) and characters[index + count] == characters[index]):
                count += 1
            characters[output_pos] = characters[index]
            output_pos += 1
            if count > 1:
                count_str = str(count)
                characters[output_pos:output_pos+len(count_str)] = list(count_str)
                output_pos += len(count_str)
            index += count
        return output_pos

This Python solution provides an effective way to compress a string array "characters" by modifying the array in-place and then returning the new length of the modified array.

• Begin by initializing an index to track the current position in the characters array and an output_pos to indicate where to write the compressed characters.
• Use a while loop to process each character until the end of the list:
  1. Initialize count to 1.
  2. Use another while loop to count contiguous identical characters.
  3. Store the current character in the compressed output position and increment output_pos.
  4. If count is greater than 1, meaning the character repeats:
     • Convert the count to a string and expand this into the list starting from output_pos.
     • Adjust output_pos by the length of the count string.
  5. Increment the index by count to skip over the already processed characters.
• At the end, output_pos gives the length of the array after compression, which is returned.

This method effectively reduces the space used whenever there are repeated characters, making it a compact and efficient solution for string compression tasks.