# Dynamic Programming with Swift

When faced with a new or difficult coding problem, it can be hard to determine the right approach. For this challenge, our goal is to identify the count of *consecutive values* in a sequence. Shown below, **longestSequence** accepts two String parameters and returns an Int:

/* write a function to identify the largest count of consecutive "1's" in the sequence. e.g. 111000011011 -> 3 */`func`

longestSequence(of key:`String`

, list: String) ->`Int`

{ //code goes here.. }

### THE ANALYSIS

Let's approach this challenge using techniques discussed in previous essays. To start, we should scan the question for patterns and discrepancies. One item to note is that hiring managers don't normally provide function signatures (e.g., stubs) when asking questions. Shown above, our goal is to determine the total count of consecutive of 1's, but this question could easily be extended to identify **characters **or specific alphanumeric sequences. We'll revisit this idea later.

Another item to note is the pattern of 1's and 0's. Based on the sample data, there are **three** groups of "1" values - these total **3, 2 and 2** respectively. These values could be stored in a collection to be analyzed. Using a data structure like a max-heap is especially plausible as its main operation works in **O(1) - constant time** and appears to match the flow of the solution. A standard Swift **Array** or **Dictionary** could also be used, but additional logic (e.g. map, filter, reduce) would be needed to calculate the largest value. Expressed as comments, let's review:

`func`

longestSequence(of key:`String`

, list:`String`

) ->`Int`

{ ... //1. iterate through input list (e.g. 11100011011) for s`in`

list { //2. tally the three groups of "1" values (e.g. 3,2,2) //3. store the values in a collection } //4. apply logic to determine largest number in the set ... }

These ideas are technically possible and should be considered. However, it would be ideal to find a solution that provides algorithmic efficiencies for both **time** and **space**. Although functional, our current design **increases** the required space by saving all possible values. As the essay title suggests, we can rewrite our plan using a simpler form of dynamic programming.

### THE IMPLEMENTATION

Dynamic programming is based on the concept of *"data storage for later reuse"*. Depending on the scenario, this can take many forms. While saving values to a collection meets our immediate needs, a streamlined solution can** **save the **current** number of consecutive values to a** single variable**. This variable could then be updated depending on the scenario. In Swift, this can be expressed as follows:

`func`

longestSequence(of key:`String`

, list:`String`

) ->`Int`

{ //initial values var current:`String`

var counter:`Int`

= 0 var longest:`Int`

= 0 //iterate through list - O(n) for s in list { //current iteration current =`String`

(s)`if`

current == key { counter += 1 }`else`

{ counter = 0 } //preserve the longest sequence`if`

counter >= longest{ longest = counter } } //return count results`return`

longest } longestSequence(of: "1", list: "11100011011")

Beyond providing space efficiencies, an additional benefit is its relatively straightforward syntax. As shown, this approach didn't require any **advanced **Swift features, structures or specific IOS SDK calls. As a result, such an approach would be feasible to write in a real interview situation (where one may be asked to write the solution on a whiteboard).

### REFINEMENT

Lastly, let's return to our first observation regarding the handling of generic input. Even though the original question didn't specifically mention *generics*, this could be a good opportunity to refine the solution to showcase our expertise:

`extension`

Array where Element:`Comparable`

{ //determine the longest sequence of specified generic values`func`

longestSequence(of key:`Element`

) ->`Int`

{ //initial values`var`

current:`Element`

`var`

counter:`Int`

= 0`var`

longest:`Int`

= 0 //iterate through list - O(n) for s in`self`

{ //current iteration current = s`if`

current == key { counter += 1 }`else`

{ counter = 0 } //preserve the longest sequence`if`

counter >= longest{ longest = counter } } //return count results`return`

longest } } let list: Array<`String`

> = ["A", "B", "B", "A"] list.longestSequence(of: "B")