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 tos
.  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
 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.
 Iteration Over Characters:
 The outer
while
loop iterates over the characters in the array withi
serving as the starting index for each sequence of identical characters.
 The outer
 Counting Identical Characters:
 For each character at position
i
, the innerwhile
loop counts how many times the character repeats by incrementingj
until it finds a different character or reaches the end of the array.
 For each character at position
 Writing the Character:
 The character at the current sequence start (
chars[i]
) is written to thek
th position in the array.
 The character at the current sequence start (
 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 currentk
position.
 If the count of the current character (
 Updating Pointers:
 After processing a sequence of identical characters,
i
is updated toj
(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.
 After processing a sequence of identical characters,
 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.
 After all characters have been processed,
Example
Given an input array ["a","a","b","b","c","c","c"]
, the function works as follows:
 Start with
i = 0
andk = 0
.  Count
a
’s: Twoa
’s found, write'a'
tochars[0]
, and'2'
tochars[1]
. Now,k = 2
.  Move to the
b
’s: Twob
’s found, write'b'
tochars[2]
, and'2'
tochars[3]
. Now,k = 4
.  Finally, count
c
’s: Threec
’s found, write'c'
tochars[4]
,'3'
tochars[5]
. Now,k = 6
.  The array now looks like
["a","2","b","2","c","3"]
, and the function returns6
.
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 inplace, 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 ji > 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 } }