LeetCode Python/Java/C++/JS  >  Array  >  443. String Compression  >  Solved in Python, Java, C++, C#, JavaScript, Go, Ruby  >  GitHub or Repost

    LeetCode link: 443. String Compression, difficulty: Medium.

    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.

    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".

    Constraints:

    • 1 <= chars.length <= 2000
    • chars[i] is a lowercase English letter, uppercase English letter, digit, or symbol.
    Hint 1

    How do you know if you are at the end of a consecutive group of characters?

    Intuition
    PreviousNext

    We use two pointers (a read pointer fast and a write pointer slow) and a counter count to achieve in-place compression.

    1. Initialization:

      • Append a sentinel character (e.g., a space " ") to the end of the input array chars. This ensures that the last group of consecutive characters can also be correctly processed within the loop. Java and C# is a little different because array is fixed size.
      • slow = 0: The slow pointer points to the starting character of the current write segment, and it also represents the length of the final compressed array.
      • count = 1: Records the number of occurrences of the current consecutive character chars[slow].

    2. Traversal and Compression:

      • The fast pointer starts traversing the array chars from index 1 (until the sentinel character).
      • Case 1: Character Repetition (chars[fast] is equal to chars[slow])
        • Increment count.
      • Case 2: Character Not Repeated (chars[fast] is not equal to chars[slow])
        • Subcase 1: Count is 1
          • Please implement it by yourself
        • Subcase 2: Count is greater than 1
          • Please implement it by yourself

    3. Return Result:

      • After the fast pointer has traversed the entire array (including the sentinel), the value of the slow pointer is the new length of the compressed array.

    Pattern of "Fast & Slow Pointers Technique" 

    int slow = 0; // slow pointer
// ...

for (int fast = 1; fast < array_length; fast++) { // This line is the key!
    if (condition_1) {
        // ...
        continue; // 'continue' is better than 'else' because 'else' will introduce more indents
    }

    if (condition_2) {
        // ...
        continue; // 'continue' is better than 'else'
    }

    // condition_3
    // ...
    slow++;
    // ...
}

return something;

    Complexity

    Time complexity

    O(N)

    Space complexity

    O(1)

    Solution in languages: Python Java C++ C# JavaScript Go Ruby

    Python # 

    class Solution:
    def compress(self, chars: List[str]) -> int:
        chars.append(" ") # Append an extra special char to process the last char easier
        slow = 0 # Slow pointer. This is the answer.
        count = 1 # Count of consecutive repeating characters

        for fast in range(1, len(chars)):
            if chars[fast] == chars[slow]:
                count += 1
                continue # 'continue' is better than 'else' because 'else' will introduce more indents

            if count == 1:
                slow += 1
                # Don't need to append the 'count' when count is 1.
                chars[slow] = chars[fast]
                continue # 'continue' is better than 'else' because 'else' will introduce more indents

            # Append the 'count'
            for c in str(count):
                slow += 1
                chars[slow] = c

            slow += 1
            chars[slow] = chars[fast]
            count = 1

        return slow

    Java # 

    import java.util.ArrayList;
import java.util.List;

class Solution {
    public int compress(char[] chars) {
        int slow = 0; // Slow pointer. This is the answer.
        int count = 1; // Count of consecutive repeating characters

        for (int fast = 1; fast <= chars.length; fast++) { // it is "<=", not "<"
            var charFast = (fast == chars.length ? ' ' : chars[fast]);

            if (charFast == chars[slow]) {
                count++;
                continue; // 'continue' is better than 'else' because 'else' will introduce more indents
            }

            if (count == 1) {
                slow++;
                // Don't need to append the 'count' when count is 1.
                if (slow < chars.length) {
                    chars[slow] = charFast;
                }
                continue; // 'continue' is better than 'else' because 'else' will introduce more indents
            }

            // Append the 'count'
            for (char c : String.valueOf(count).toCharArray()) {
                slow++;
                chars[slow] = c;
            }

            slow++;
            if (slow < chars.length) {
                chars[slow] = charFast;
            }
            count = 1;
        }

        return slow;
    }
}

    C++ # 

    class Solution {
public:
    int compress(vector<char>& chars) {
        chars.push_back(' '); // Append an extra special char to process the last char easier
        int slow = 0; // Slow pointer. This is the answer.
        int count = 1; // Count of consecutive repeating characters

        for (int fast = 1; fast < chars.size(); ++fast) {
            if (chars[fast] == chars[slow]) {
                count++;
                continue; // 'continue' is better than 'else' because 'else' will introduce more indents
            }

            if (count == 1) {
                slow++;
                // Don't need to append the 'count' when count is 1.
                chars[slow] = chars[fast];
                continue; // 'continue' is better than 'else' because 'else' will introduce more indents
            }

            // Append the 'count'
            for (char c : to_string(count)) {
                slow++;
                chars[slow] = c;
            }

            slow++;
            chars[slow] = chars[fast];
            count = 1;
        }

        return slow;
    }
};

    C# # 

    public class Solution
{
    public int Compress(char[] chars)
    {
        int slow = 0; // Slow pointer. This is the answer.
        int count = 1; // Count of consecutive repeating characters

        for (int fast = 1; fast <= chars.Length; fast++)
        { // it is "<=", not "<"
            char charFast = (fast == chars.Length ? ' ' : chars[fast]);

            if (charFast == chars[slow])
            {
                count++;
                continue; // 'continue' is better than 'else' because 'else' will introduce more indents
            }

            if (count == 1)
            {
                slow++;
                // Don't need to append the 'count' when count is 1.
                if (slow < chars.Length)
                {
                    chars[slow] = charFast;
                }
                continue; // 'continue' is better than 'else' because 'else' will introduce more indents
            }

            // Append the 'count'
            foreach (char c in count.ToString())
            {
                slow++;
                chars[slow] = c;
            }

            slow++;
            if (slow < chars.Length)
            {
                chars[slow] = charFast;
            }
            count = 1;
        }

        return slow;
    }
}

    JavaScript # 

    /**
 * @param {character[]} chars
 * @return {number}
 */
var compress = function(chars) {
    chars.push(' ') // Append an extra special char to process the last char easier
    let slow = 0 // Slow pointer. This is the answer.
    let count = 1 // Count of consecutive repeating characters

    for (let fast = 1; fast < chars.length; fast++) {
        if (chars[fast] === chars[slow]) {
            count++
            continue // 'continue' is better than 'else' because 'else' will introduce more indents
        }

        if (count === 1) {
            slow++
            // Don't need to append the 'count' when count is 1.
            chars[slow] = chars[fast]
            continue // 'continue' is better than 'else' because 'else' will introduce more indents
        }

        // Append the 'count'
        for (const c of count.toString()) {
            slow++
            chars[slow] = c
        }

        slow++
        chars[slow] = chars[fast]
        count = 1
    }

    return slow
}

    Go # 

    // A test cannot pass. Reason is still unknown

func compress(chars []byte) int {
    chars = append(chars, ' ') // Append an extra special char to process the last char easier
    slow := 0 // Slow pointer. This is the answer.
    count := 1 // Count of consecutive repeating characters

    for fast := 1; fast < len(chars); fast++ {
        if chars[fast] == chars[slow] {
            count++
            continue // 'continue' is better than 'else' because 'else' will introduce more indents
        }

        if count == 1 {
            slow++
            // Don't need to append the 'count' when count is 1.
            chars[slow] = chars[fast]
            continue // 'continue' is better than 'else' because 'else' will introduce more indents
        }

        // Append the 'count'
        for _, c := range strconv.Itoa(count) {
            slow++
            chars[slow] = byte(c)
        }

        slow++
        chars[slow] = chars[fast]
        count = 1
    }

    return slow
}

    Ruby # 

    # @param {Character[]} chars
# @return {Integer}
def compress(chars)
  chars << " " # Append an extra special char to process the last char easier
  slow = 0 # Slow pointer. This is the answer.
  count = 1 # Count of consecutive repeating characters

  (1...chars.length).each do |fast|
    if chars[fast] == chars[slow]
      count += 1
      next # 'next' is better than 'else' because 'else' will introduce more indents
    end

    if count == 1
      slow += 1
      # Don't need to append the 'count' when count is 1.
      chars[slow] = chars[fast]
      next # 'next' is better than 'else' because 'else' will introduce more indents
    end

    # Append the 'count'
    count.to_s.each_char do |c|
      slow += 1
      chars[slow] = c
    end

    slow += 1
    chars[slow] = chars[fast]
    count = 1
  end

  slow
end
    Solution in languages: Python Java C++ C# JavaScript Go Ruby

    Other languages

    Welcome to contribute code to LeetCode.to GitHub -> 443. String Compression. Thanks!
    PreviousNext