3163. String Compression III

MediumString

Problem Description

Given a string word, compress it using the following algorithm:

Begin with an empty string comp. While word is not empty, perform the following operation:
- Remove a maximum length prefix of word that consists of a single character c repeating at most 9 times.
- Append the length of the prefix followed by c to comp.

Return the string comp.

Intuition

The key idea behind this problem is to encode contiguous blocks of the same character in a compressed form that shows both the count and the character itself, with a limit of 9 on the count.

The solution involves utilizing a groupby function for handling sequences of repeated characters. For each character group:

Count its sequential occurrence (k).
As the maximum allowed count is 9, split k into chunks where each chunk, x, is at most 9.
For each chunk, append a string formed by concatenating x and the character to the result list.

This approach effectively compresses the string without exceeding the maximum count constraint.

Solution Approach

The solution uses the groupby function to identify and group consecutive identical characters from the input string word. Here's a breakdown of the approach:

Initialize Variables:
- Use groupby to iterate through word, grouping repeated characters together.
- Create an empty list ans to store the compressed parts of the string.
Iterate Over Groups:
- For each character c in the group and its corresponding values v:
  - Determine the length k of the current group.
Divide Group into Chunks:
- Since we can only repeat a character up to 9 times in the compressed form, divide the length k into chunks where each chunk x is at most 9.
- For each chunk:
  - Append the compression form str(x) + c to ans.
Build the Result:
- Join all elements in ans to form the final compressed string.

By iterating through the groups and managing the maximum limit on repetition, the algorithm efficiently compresses the input string according to the specified rules.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's go through the solution with a simple example: word = "aaabbbcccccccccddddeeeeeeeff". We want to compress this string using the approach described.

Initialization:
- We start with an empty list ans that will hold parts of our compressed string.
Using groupby:
- We iterate through the string using the groupby function, which helps us identify contiguous blocks of the same character.
- In this example, groupby will produce the following groups:
  - 'a' → ['a', 'a', 'a']
  - 'b' → ['b', 'b', 'b']
  - 'c' → ['c', 'c', 'c', 'c', 'c', 'c', 'c', 'c', 'c'] (9 'c's)
  - 'd' → ['d', 'd', 'd', 'd']
  - 'e' → ['e', 'e', 'e', 'e', 'e', 'e', 'e']
  - 'f' → ['f', 'f']
Processing Each Group:
- For each group, we determine the length of the occurrences (k).
- The group of 'a's is handled first:
  - Length k = 3. We add 3a to ans.
- Next, the group of 'b's:
  - Length k = 3. We add 3b to ans.
- Then, the group of 'c's:
  - Length k = 9. Since this equals the maximum chunk size, we add 9c to ans.
- For the group of 'd's:
  - Length k = 4. We add 4d to ans.
- Processing the group of 'e's:
  - Length k = 7. We add 7e to ans.
- Finally, the group of 'f's:
  - Length k = 2. We add 2f to ans.
Building the Result:
- The final step is joining all parts in ans to form the compressed string: "3a3b9c4d7e2f".

This provides a compact representation of the original string while adhering to the rule of not exceeding 9 repetitions within a single compressed part.

Solution Implementation

1from itertools import groupby
2
3class Solution:
4    def compressedString(self, word: str) -> str:
5        # Use groupby to group adjacent characters in the input string
6        grouped_characters = groupby(word)
7        compressed_result = []
8      
9        # Iterate through each group of characters
10        for character, same_character_group in grouped_characters:
11            count = len(list(same_character_group))  # Count the size of the group
12          
13            # Encode the character count in chunks of maximum 9
14            while count > 0:
15                chunk_size = min(9, count)
16                # Append the compressed format (digit + character) to the result
17                compressed_result.append(str(chunk_size) + character)
18                count -= chunk_size
19      
20        # Join all parts of the compressed result into a single string
21        return "".join(compressed_result)
22

1class Solution {
2    public String compressedString(String word) {
3        // StringBuilder to construct the compressed string
4        StringBuilder ans = new StringBuilder();
5
6        // Length of the input word
7        int n = word.length();
8
9        // Loop through the word to process each character
10        for (int i = 0; i < n;) {
11            // Start j from the next character of i
12            int j = i + 1;
13
14            // Increment j while the next character is the same as the current character
15            while (j < n && word.charAt(j) == word.charAt(i)) {
16                ++j;
17            }
18
19            // Calculate the number of repeating characters
20            int k = j - i;
21
22            // Process the repeats in chunks of up to 9
23            while (k > 0) {
24                // Take the minimum of 9 or remaining repeats to handle
25                int x = Math.min(9, k);
26
27                // Append the count and character to the result
28                ans.append(x).append(word.charAt(i));
29
30                // Decrease k by the chunk size handled
31                k -= x;
32            }
33
34            // Move i to the next new character
35            i = j;
36        }
37      
38        // Return the compressed string
39        return ans.toString();
40    }
41}
42

1class Solution {
2public:
3    // Method to compress a given string by counting consecutive characters
4    string compressedString(string word) {
5        string ans; // String to store the compressed result
6        int n = word.length(); // Length of the input word
7
8        // Iterate through the word
9        for (int i = 0; i < n;) {
10            int j = i + 1;
11
12            // Count consecutive occurrences of the current character
13            while (j < n && word[j] == word[i]) {
14                ++j;
15            }
16          
17            int k = j - i; // Number of consecutive characters
18
19            // Handle each group of identical characters
20            while (k > 0) {
21                int x = min(9, k); // Process up to 9 characters at a time for compression
22                ans.push_back('0' + x); // Append the count as a character
23                ans.push_back(word[i]); // Append the character itself
24                k -= x; // Reduce the remaining count of characters to process
25            }
26          
27            i = j; // Move to the next new character
28        }
29
30        return ans; // Return the compressed string
31    }
32};
33

1function compressedString(word: string): string {
2    const result: string[] = []; // Array to store compressed parts of the string
3    const length: number = word.length; // Length of the input string
4
5    for (let i = 0; i < length; ) {
6        let j = i + 1;
7      
8        // Find the segment of consecutive repeating characters starting from index 'i'
9        while (j < length && word[j] === word[i]) {
10            ++j;
11        }
12
13        let segmentLength = j - i; // Length of the segment of repeated characters
14
15        while (segmentLength > 0) {
16            // Compress the segment length by chunks of at most 9
17            const chunkSize = Math.min(segmentLength, 9);
18            result.push(chunkSize.toString() + word[i]);
19            segmentLength -= chunkSize;
20        }
21
22        i = j; // Move to the next new character
23    }
24
25    return result.join(''); // Join the compressed parts into a single string and return
26}
27

Time and Space Complexity

The time complexity of the code is O(n). This is because the groupby function from the itertools module iterates over the input string word exactly once, grouping consecutive identical characters together. For each group of characters, the loop processes them in constant time by appending substrings with counts to the ans list.

The space complexity of the code is O(n). This is due to the storage of the resulting compressed string in the ans list. In the worst case, the length of the ans list will be proportional to the length of the input string, as each character may be represented in the compressed format.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don’t know