Welcome to Subscribe On Youtube

443. String Compression

Description

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.

Solutions

  1. Initialization:
    • i is the read pointer, starting at the beginning of the array.
    • k is the write pointer, indicating where the next compressed character should be written.
    • n is the total number of characters in the input array.
  2. Iteration Over Characters:
    • The outer while loop iterates over the characters in the array with i serving as the starting index for each sequence of identical characters.
  3. Counting Identical Characters:
    • For each character at position i, the inner while loop counts how many times the character repeats by incrementing j until it finds a different character or reaches the end of the array.
  4. Writing the Character:
    • The character at the current sequence start (chars[i]) is written to the k-th position in the array.
  5. Writing the Count (if applicable):
    • If the count of the current character (j - i) is greater than 1, the code converts this count to a string (cnt) and iterates over each character in this string, writing them sequentially to the array starting from the current k position.
  6. Updating Pointers:
    • After processing a sequence of identical characters, i is updated to j (the index following the last identical character), and the process repeats.
    • k is incremented as characters (and counts, when applicable) are written to the array.
  7. Returning the Length:
    • After all characters have been processed, k represents the new length of the compressed character array, which is returned as the solution.

Example

Given an input array ["a","a","b","b","c","c","c"], the function works as follows:

  • Start with i = 0 and k = 0.
  • Count a’s: Two a’s found, write 'a' to chars[0], and '2' to chars[1]. Now, k = 2.
  • Move to the b’s: Two b’s found, write 'b' to chars[2], and '2' to chars[3]. Now, k = 4.
  • Finally, count c’s: Three c’s found, write 'c' to chars[4], '3' to chars[5]. Now, k = 6.
  • The array now looks like ["a","2","b","2","c","3"], and the function returns 6.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the input array. Each element is processed once.
  • Space Complexity: O(1), as the compression is done in-place, and only a constant amount of extra space is used.

Follow up

If a follow up question asking for the compressed result, simply return

    return chars[:k];

  • class Solution {
    public int compress(char[] chars) {
        int k = 0, n = chars.length;
        for (int i = 0, j = i + 1; i < n;) {
            while (j < n && chars[j] == chars[i]) {
                ++j;
            }
            chars[k++] = chars[i];
            if (j - i > 1) {
                String cnt = String.valueOf(j - i);
                for (char c : cnt.toCharArray()) {
                    chars[k++] = c;
                }
            }
            i = j;
        }
        return k;        
    }
}

  • class Solution {
public:
    int compress(vector<char>& chars) {
        int k = 0, n = chars.size();
        for (int i = 0, j = i + 1; i < n;) {
            while (j < n && chars[j] == chars[i])
                ++j;
            chars[k++] = chars[i];
            if (j - i > 1) {
                for (char c : to_string(j - i)) {
                    chars[k++] = c;
                }
            }
            i = j;
        }
        return k;
    }
};

  • class Solution:
    def compress(self, chars: List[str]) -> int:
        i, k, n = 0, 0, len(chars)
        while i < n:
            j = i + 1
            while j < n and chars[j] == chars[i]:
                j += 1
            chars[k] = chars[i]
            k += 1
            if j - i > 1:
                cnt = str(j - i)
                for c in cnt:
                    chars[k] = c
                    k += 1
            i = j
        return k

        '''
        if a follow up question asking for the compressed result, simply return

            return chars[:k];
        '''


  • func compress(chars []byte) int {
	i, k, n := 0, 0, len(chars)
	for i < n {
		j := i + 1
		for j < n && chars[j] == chars[i] {
			j++
		}
		chars[k] = chars[i]
		k++
		if j-i > 1 {
			cnt := strconv.Itoa(j - i)
			for _, c := range cnt {
				chars[k] = byte(c)
				k++
			}
		}
		i = j
	}
	return k
}

  • impl Solution {
    pub fn compress(chars: &mut Vec<char>) -> i32 {
        let (mut i, mut k, n) = (0, 0, chars.len());
        while i < n {
            let mut j = i + 1;
            while j < n && chars[j] == chars[i] {
                j += 1;
            }
            chars[k] = chars[i];
            k += 1;

            if j - i > 1 {
                let cnt = (j - i).to_string();
                for c in cnt.chars() {
                    chars[k] = c;
                    k += 1;
                }
            }
            i = j;
        }
        k as i32
    }
}

All Problems

All Solutions