Let X$[1$ : n$]$ be an array of characters. A run is any maximal sequence of consecutive identical

elements in the array, and the length of a run is the number of entries in it$.$ Each run is

represented as a triplet $($i$,$j$,$a$),$ where i is the index of the starting element of the run, j is the index

of the ending element of the run, and $$ is the repeating character of the run. For example, in the

array

$,,,,,,,,,,,,,$

the runs are: $[,,,,]($represented as $(1,5,)),[,,,]($represented as $(6,9,)),[,]$

$($represented as $(10,11,)),$ and $[,,]($represented as $(12,14,)).$

a$.$ Write a divide$-$and$-$conquer algorithm that takes as input a character array X$[1$ : n$],$ and

returns a list of the $($i$,$j$,$a$)$ triplets for the runs in the input array. Analyze the time complexity

of your algorithm. $($Your algorithm should split the input into two halves$)$

b$.$ Write a divide$-$and$-$conquer algorithm that returns the longest run in an input real array.

Analyze the time complexity of your algorithm. $($Your algorithm should split the input into

two halves, and must not use the output of the algorithm of part $($a$))$