Leetcode 38: The “count-and-say” sequence

Question

38. Count and Say

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 is read off as "one 1" or 11.

11 is read off as "two 1s" or 21.

21 is read off as "one 2, then one 1" or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

With iteration:

How to reduce 3 kinds of situation to one solution?

class Solution {
    func countAndSay(_ n: Int) -> String {
        var ans = ["1"]
        var temp: [String], j: Int
        for _ in 1..<n{
            //  from the beginning 1 to what we what
            j = 1
            temp = []
            for i in 1..<ans.count{
                if ans[i - 1] == ans[i]{
                    j += 1
                    //  Situation one: the current is equal to the previous ( util the last )
                }
                else{
                    temp.append(String(j))
                    temp.append(ans[i-1])
                    //  Situation two: the current is not equal to the previous ( util the last )
                    j = 1
                }
            }
            //  Situation three: the last value
            temp.append(String(j))
            temp.append(ans.last!)
            ans = temp
            print(ans.reduce("", +))
        }
        return ans.reduce("", +)
    }
}

With Recursion, which is a little leaner.

class Solution {
    func countAndSay(_ n: Int) -> String {
        if n == 1 {
            return "1"
        }
        let str = countAndSay(n-1)
        let arr = Array(str).map{Int(String($0))}
        var last = arr[0]!
        var temp : [(count: Int, val: Int)] = [(1, last)]
        for num in arr[1...]{
            if last == num{
                var final = temp.last!
                final.count += 1
                temp.removeLast()
                temp.append(final)
            }
            else{
                temp += [(1, num!)]
            }
            last = num!
        }
        var result = ""
        for key in temp{
            result += "\(key.0)\(key.1)"
        }
        return result
    }
}

How to go on doing some improvement?

Answer 1

Your iterative solution

This is generally fine, with the only exception that it operates on an array of strings –  I'll come back to that later.

Variables should be defined in the narrowest scope where they are used. This applies to

var temp: [String], j: Int

which are used only in the inner loop. Both variable names are non-descriptive and can be improved (e.g.: j actually counts the number of consecutive equal numbers).

Your recursive solution

Here

let arr = Array(str).map{Int(String($0))}

the conversion from str to an array is not needed: A Swift string is a collection of its characters, and you can call map() directly on the string. You also know that the string contains only decimal digits. Therefore you can force-unwrap here, replacing several force-unwraps in the following code:

let arr = str.map{ Int(String($0))! }

This

var final = temp.last!
final.count += 1
temp.removeLast()
temp.append(final)

is more simply and more efficiently done as

temp[temp.count - 1].count += 1

And this loop

var result = ""
for key in temp{
    result += "\(key.0)\(key.1)"
}
return result

can be simplified using map():

return temp.map { "\($0.count)\($0.val)" }.joined()

Generally, this looks less efficient to me than the first approach, because a string is converted to an integer array in each recursion step.

Redesign

In order to avoid unnecessary conversions between strings, characters, and integers, I would suggest to operate on an integer array generally, and create the string answer only as the final step.

Instead of an inner loop or recursion I would put the code to compute the next iteration into a separate function. That makes the code easier to read and to test:

class Solution {
    func countAndSay(_ n: Int) -> String {
        var seq = [1]
        for _ in 1..<n {
            seq = transform(seq)
        }
        return seq.map(String.init).joined()
    }

    func transform(_ seq: [Int]) -> [Int] {
        // ... TODO ...
    }
}

This works with both your solutions. For your first solution the transform function would be something like this:

func transform(_ seq: [Int]) -> [Int] {
    var result = [Int]() // The transformed sequence
    var current = seq[0] // The current number
    var count = 1 // Counts # of consecutive equal numbers
    for num in seq.dropFirst() {
        if num == current {
            count += 1
        } else {
            result.append(count)
            result.append(current)
            current = num
            count = 1
        }
    }
    result.append(count)
    result.append(current)
    return result
}

Instead of comparing against arr[i-1] the current number is “remembered” in a local variable, so that we can iterate over the sequence (without its first element) instead of iterating over the array indices.

Your second solution creates an array of (count, value) tuples first, and therefore does not need to handle the case of the last run separately. If you start with an empty array of tuples (and use optional chaining to compare against the last value) then you even don't have to handle the first value separately:

func transform(_ seq: [Int]) -> [Int] {

    var pairs: [(count: Int, val: Int)] = []
    for num in seq {
        if num == pairs.last?.val {
            pairs[pairs.count - 1].count += 1
        } else {
            pairs.append((count: 1, val: num))
        }
    }
    return Array(pairs.map { [$0.count, $0.val] }.joined())
}

In my tests this was a bit faster than your original solution, but slower than the first approach, probably because of the intermediate array.

A third solution

Here is another possible solution, which combines the advantages of both approaches. Instead of traversing the array elements, we directly search for the next index of a number different from the current. Neither the first nor the last run has be be treated specially:

func transform(_ seq: [Int]) -> [Int] {
    var result = [Int]()
    var fromIndex = seq.startIndex // Start index of current run
    while fromIndex != seq.endIndex {
        let current = seq[fromIndex]
        // Start index of next run:
        let toIndex = seq[(fromIndex+1)...].firstIndex(where: { $0 != current }) ?? seq.endIndex
        result.append(toIndex - fromIndex)
        result.append(current)
        fromIndex = toIndex
    }
    return result
}

Answer 2

Iterative vs Recursive

For code efficiency, I personally always prefer the iterative approach. According to LeetCode :

• You iterative code clocked at 12ms on Leetcode, being 3 times as fast as your recursive approach (36ms).
• It uses less memory 18.7MB, vs 19.2MB for the recursive solution.

Now let's dig in to see what could be improved :

Iterative approach

• On Leetcode, or whenever you're benchmarking your code, printing to the console would slow down the execution time dramatically. The previous execution times are given without print(ans.reduce("", +))

• I see that you've used an array of strings to ease the access to characters at a given index. You could do the same thing with String.Index and it would spare you the excess memory allocations :

  var ans = "1"
  var temp: String, j: Int
  for _ in 1..<n {
      //  from the beginning 1 to what we what
      j = 1
      temp = ""
      for i in ans.indices.dropFirst() {
          //  Situation one: the current is equal to the previous ( util the last )
          if ans[ans.index(before: i)] == ans[i] {
              j += 1
          }
          //  Situation two: the current is not equal to the previous ( util the last )
          else {
              temp.append(String(j))
              temp.append(ans[ans.index(before: i)])
              j = 1
          }
      }
      //  Situation three: the last value
      temp.append(String(j))
      temp.append(String(ans.last!))
      ans = temp
  }
  

This reduces memory usage slightly to 18.6MB. But the execution time was on average 16ms (varied from 12ms to 20ms on Leetcode). This could be due to .count and subscripting being O(n) on a String: a String in Swift is not randomAccess, unlike an array. Just to check, I tried it on TIO, and it gave the edge to the String.Index version. Anyway, in the rest of this answer, I'll revert to using an array for clarity.

• 3 for the price of one : This is the direct answer to your question, and all it takes is adjusting the bounds of the inner loops (the forced-unwrapping was calling for this change) :

  for _ in 1..<n {
      var temp: [String] = []
      var i = 0
      while i < ans.count {
          let char = ans[i]
          var j = 0
          while i < ans.count && ans[i] == char {
              j += 1
              i += 1
          }
          temp.append(String(j))
          temp.append(char)
      }
      ans = temp
  } 
  

Notice that the outer loop was chosen as a for loop, since it is faster than a while loop in Swift, since the latter checks the condition on each iteration. Try It Online!

• ans.reduce("", +) can be simply written as ans.joined()

• Instead of using arrays of strings that contains one character only, better use arrays of the less expensive type: Character.

Putting it all together :

class Solution {
    func countAndSay(_ n: Int) -> String {
        var ans: [Character] = ["1"]
        for _ in 1..<n {
            var temp: [Character] = []
            var i = 0
            while i < ans.count {
                let char = ans[i]
                var j = 0
                while i < ans.count && ans[i] == char {
                    j += 1
                    i += 1
                }
                temp.append(Character(String(j)))
                temp.append(char)
            }
            ans = temp
        }
        return String(ans)
    }
}

Leetcode : Runtime: 12 ms, Memory Usage: 18.8 MB

Recursive approach

• Personally, I find it more idiomatic to use the guard statement instead of an if condition in an (very) early return :

  guard 1 < n else {
       return "1"
  }
  

Notice that I've used the < since it is the one defined by default, and no protocol witnesses would be generated at runtime for it. This a very slight improvement, and you could try it online.

• arr is an array of optional Ints, which is unnecessary since we're sure that all characters of str are convertible to Int. So, we'd better use compactMap. That would spare you force unwrapping last and num :

  let arr = Array(str).compactMap{Int(String($0))}
  

This change alone brings the execution time from 36ms to 32ms.

Or, force unwrap inside the map closure :

let arr = Array(str).map{Int(String($0))!}

which brings the runtime to 28ms.

• Using string interpolation is really slow, better use a String initializer:

  result += String(key.0) + String(key.1)
  

Alternative recursive implementation:

Here is an alternative implementation that clocks at 16ms, 18.4MB :

class Solution {
    func countAndSay(_ n: Int) -> String {
        guard 1 < n else {
            return "1"
        }
        let str = countAndSay(n - 1)
        var ans = ""
        var count = 0
        var i = str.startIndex
        while i < str.endIndex {
            count += 1
            let indexfterI = str.index(after: i)
            if (indexfterI < str.endIndex && str[indexfterI] != str[i]) ||
                indexfterI == str.endIndex {
                ans += String(count) + String(str[i])
                count = 0
            }
            i = indexfterI
        }
        return ans
    }
}

Taking advantage of the problem description

Since n is less than 30, you can generate all the answers from 1, to 30, put them in an array, and return the element corresponding to n :

class Solution {
    func countAndSay(_ n: Int) -> String {
        return a[n]
    }
    let a = ["", "1", "11", "21", "1211", "111221", "312211", ... ] //31 elements
}

This hack clocks at 8ms.

Answer 3

For what it’s worth, when I see a progression like this, I lean towards Sequence/Iterator pattern, e.g.:

struct CountAndSayIterator<T>: IteratorProtocol where T: RangeExpression, T.Bound == Int {
    private let range: T
    private var currentValue: String = ""
    private var currentIndex: Int = 0

    init(_ range: T) {
        self.range = range

        // burn off values if we have to

        while !range.contains(currentIndex) {
            calculateNext()
        }
    }

    mutating func next() -> String? {
        guard range.contains(currentIndex) else {
            return nil
        }

        return calculateNext()
    }

    @discardableResult
    private mutating func calculateNext() -> String? {
        currentIndex += 1

        if currentValue.isEmpty {
            currentValue = "1"
            return currentValue
        }

        var iterator = currentValue.makeIterator()

        guard var previousCharacter: Character = iterator.next() else { return nil }
        var count = 1

        var character: Character?
        var result = ""

        repeat {
            character = iterator.next()
            switch character {
            case previousCharacter:
                count += 1

            default:
                result += "\(count)\(previousCharacter)"
                if let character = character {
                    previousCharacter = character
                    count = 1
                }
            }
        } while character != nil

        currentValue = result
        return result
    }
}

struct CountAndSaySequence<T>: Sequence where T: RangeExpression, T.Bound == Int {
    let range: T

    init(_ range: T) {
        self.range = range
    }

    func makeIterator() -> CountAndSayIterator<T> {
        return CountAndSayIterator(range)
    }
}

Then you can do natural things like:

for value in CountAndSaySequence(0..<5) {
    print(value)
}

Or

let array = Array(CountAndSaySequence(0...4))
print(array)

And, when you have this Iterator that calculates the values for you, you can implement the requested method like so:

func countAndSay(_ n: Int) -> String {
    var iterator = CountAndSayIterator(n...)
    return iterator.next()!
}

Clearly, I’m using a zero-based index and this question, despite our living in a zero-based world, is using 1-based index, so adjust that countAndSay method as you see fit.

And, obviously, if you wanted, you could further extend this CountAndSaySequence type to be a Collection with caches for previously calculated values, etc. But that seemed beyond the scope of this question.

But using Sequence feels a bit swiftier to me.