Search⌘ K
Home
Courses
Decode the Coding Interview in Rust: Real-World Examples

Feature #8: Compress File II

Explore how to implement basic file compression that replaces repeated characters with the character followed by its count, all while modifying the text in place using constant extra space. Understand the O(n^2) time complexity involved in compressing character lists and how to handle repeated characters efficiently in Rust.

We'll cover the following...

Description

The ability to compress files is an essential functionality that can come in handy. In this feature, we will learn how to carry out basic file compression, just like the one that WinZip does. The file compression process will compress text files by replacing multiple consecutive occurrences of the same character with that character followed by the number of its consecutive occurrences. If a character does not have any consecutive repetitions, then we will just write the character to the output. For example, "abbbbccc" will become "ab4c3". Our task will be to return the compressed file using constant additional space.

Note: Suppose that 'a' repeats 15 times. In that case, we will compress it like this: ['a', '1', '5']

We will be provided with a character list that will represent the text in a file.

Solution

We will make changes to the original list and return it as a compressed file because we can only use constant space. Here is the algorithm that we will use:

  • Count the continuous occurrences of a character.
  • Remove all but one occurrence of that character.
  • Insert the character’s count after it in the list.
  • Repeat this process.

Let’s see how the whole process will work:

Let’s look at the code for this solution:

Rust 1.57.0
fn compress(chars:&mut Vec<char>)->Vec<char> {
    let mut i = 0;
    while i < chars.len(){
      let mut count = 1;
      let ch = chars[i];
      i+=1;
      let mut c = i;
      
      // Count the number of times a character repeats
      while i < chars.len() && chars[i] == ch{
        chars.remove(i);
        count+=1;
      } 
        // Insert the count
      if count > 1{
        let s = count.to_string();
        for sc in s.chars(){
          chars.insert(c,sc);
          c+=1;
        }
         
      }
      
    }
    return chars.to_vec();
  }
fn main(){
  let mut chars: Vec<char> = vec!['a','a','b','b','b','c','a','a','a','a'];
  println!("{:?}",compress(&mut chars));
}

Complexity measures

Time complexity Space complexity
O(n2)
...