Coding Interview. String Compression Challenge

Task description

Given a string, write a function that accepts this string as input and returns compressed string. Algorithm of compression is following: every sequence of the same character should be replaced with that character followed by the number of repetitions. If the compressed string is longer than the original string, then function should return the original string.

Algorithm for this challenge also known as Run Length Encoding.

Examples of input and output

• a becomes a (because a1 is not shorter than a)
• aa becomes aa (because a2 is not shorter than aa)
• aaa becomes a3
• abc becomes abc (because a1b1c1 is not shorter than abc)
• aabbbdcccc becomes a2b3d1c4
• aaabbbccc becomes a3b3c3
• aabbbcccdeee becomes a2b3c3d1e3

Swift Implementation Prerequisites

In Swift we cannot get character of string by it's integer index. If we try to do this we will have an error. 

let test = "aaabbbbdcccee"

for i in 0..<(test.count - 1) {
    let ch = test[i] // error
}

'subscript' is unavailable: cannot subscript String with an Int, see the documentation comment for discussion

For getting character we must calculate "String.Index" value first.  

for i in 0..<(test.count - 1) {
    let index = test.index(test.startIndex, offsetBy: i)
    let character = test[index]
    print(character)
}

For simplifying this we can make subscript method for String type and get character by index.

let test = "aaabbbbdcccee"

extension String {
    
    subscript (i: Int) -> Character {
        let index = self.index(self.startIndex, offsetBy: i)
        let character = self[index]
        return character
    }
}

print(test[0]) // a
print(test[3]) // b
print(test[test.count - 1]) // e

Algorithm

1. Create variables 
• result for compressed string
• sum for counting each character
2. For loop from 0 to n-2 (where n = length of string, n - 2 because we will compare current and next characters)
• Compare current and next characters
• If they are equal add 1 to sum
• Else append current character and sum to result and reset sum to 0
3. Append to result last character and sum (because in for loop we update result only in case of characters are changed).
4. Compare lengths of initial and compressed strings and return one with less length.

Swift Implementation

let test1 = "abbbc"
let test2 = "aaa"
let test3 = "abc"
let test4 = "aabbbcccdeee"

func compress(_ str: String) -> String {
    var result = ""
    var sum = 1
    for i in 0..<(str.count - 1) {
        if (str[i] == str[i + 1]) {
            sum += 1
        } else {
            result += "\(str[i])\(sum)"
            sum = 1
        }
    }
    result += "\(str[str.count - 1])\(sum)"
    return result.count < str.count ? result : str
}

print(compress(test1)) // abbbc -> abbbc
print(compress(test2)) // aaa -> a3
print(compress(test3)) // abc -> abc
print(compress(test4)) // aabbbcccdeee -> a2b3c3d1e3

We can improve algorithm

1. Initially assign 0 to sum
2. For loop from from 0 to n-1
3. Increase sum by 1 in each iteration
4. In each iteration check if it is the end of string or current and next characters are different. If Condition is true than append current character and sum to result and reset sum to 0.

func compress_v2(_ str: String) -> String {
    var result = ""
    var sum = 0
    for i in 0..<str.count {
        sum += 1
        if (i + 1 == str.count) || (str[i] != str[i + 1]) {
            result += "\(str[i])\(sum)"
            sum = 0
        }
    }
    return result.count < str.count ? result : str
}

More "Swifty" Implementation

But there could be more "swifty" solution without using string index. We can use for each loop for string characters.

Algorithm

1. Create three variables: 
• currentCharacter - optional variable for current character
• sum - counter for for each character
• result - compressed string
2. For loop for each character in string
• If character is equal to currentCharacter then add 1 to sum
• Else do following
• Check that currentCharacter has value and if it has then add this value and sum to result
• Save character into currentCharacter
• Reset sum to 1
3. After loop finished, append currentCharacter and sum to the result string. (This step can be easily forgotten, because in for loop we only modify result string in case of character changes.)
4. Compare lengths of initial and compressed strings and return one with less length.

func compress_v3(_ str: String) -> String {
    var currentCharacter: Character?
    var sum = 0
    var result = ""
    for ch in str {
        if ch == currentCharacter {
            sum += 1
        } else {
            if let current = currentCharacter {
                result.append("\(current)\(sum)")
            }
            currentCharacter = ch
            sum = 1
        }
    }
    if let current = currentCharacter {
        result.append("\(current)\(sum)")
    }
    return result.count < str.count ? result : str
}

print(compress_v3(test1)) // abbbc -> abbbc
print(compress_v3(test2)) // aaa -> a3
print(compress_v3(test3)) // abc -> abc
print(compress_v3(test4)) // aabbbcccdeee -> a2b3c3d1e3

Complexity

Because we have only one for loop - space complexity of this algorithm will be linear - O(n).

Source Code 

Source code of from this post could be found here on GitHub