Decode the Coding Interview in Swift: Real-World Examples/

...

/

Feature #8: Compress File II

Feature #8: Compress File II

Implement the "Compress File II" feature for our "Operating System" project.

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:

func compress(chars: inout [Character]) -> [Character] {
    
    var i: Int = 0
    var count: Int = 0
    var c: Int = 0
    while i < chars.count {
      count = 1
      let ch: Character = chars[i]
      i += 1
      c = i
      // Count the number of times a character repeats
      while i < chars.count && chars[i] == ch {
          chars.remove(at: i)
          count += 1
      }
      
      if count > 1 {
        // Insert the count
        
        for item in String(count) {
          chars.insert(item, at: c)
          c += 1
        }
        i = c
      }
      
    }
    return chars
  }
  // your code goes here
  var chars: [Character] = ["a","a","b","b","b","c","a","a","a","a", "4", "4", "4", "4"]
  let result: [Character] = compress(chars: &chars)
  print(String(result))
Compress file

Complexity measures

Time complexity Space complexity
...
Access this course and 1400+ top-rated courses and projects.