$**$ pls use diagrams to explaine problem$1$ part a$**$

Problem Statement

You are given string S$.$ Your goal is to design an algorithm that creates segments from the

content of the string encoded as follows: if a segment contains a single character repeated n times,

it should be encoded as $($character$)($n$)($e$.$g$.,$aaa$$ becomes $$a$3,$ and $$AA$$ becomes A$2).$ If a

segment contains a mix of unique characters $($each appearing exactly once$),$ it should be encoded

by simply concatenating those characters $($e$.$g$.,$abc$$ becomes $$abc$,$ or $$p$$ becomes $$p$).$ The

algorithm should aim to compress the length of the original string.

$$ Problem Constraints:

$$ Students MUST solve this problem using a Divide and Conquer approach,

only. No credit will be given for other approaches used.

$$ String S contains alphanumeric characters $($including symbols$)$ from the English alphabet.

Letters may be uppercase and lowercase, and may be organized into words.

$$ There may be word spacing between words in string S$.$ Words spacing must also be

considered in this problem and must be marked with the symbol $$.$ For example, $,$

will become $$$$4$ because it has $4$ word spacing

$$ The order of the string S must be preserved. For example, $$aabaa$$ IS NOT $$a$4$b$$ or

$$ba$4.$ Instead, it will become $$a$2$ba$2$

$$ The length of string S is between $1$ and $104.$

$$ The implementation of the Divide and Conquer approach for this problem MUST BE

recursive.

$$ The algorithm MUST have a constant space complexity of $\backslash$Theta $(1)$

$$ Input Format:

$$ A string S of size n

$$ Output Format:

$$ A string S of size m where m $<=$ n

$$ Example:

$$ Input: a string S $=$PPPphhhyssssssssiccccccs issss thhhEEE uuuunIveRRRRssssse$$s

oPPpppeeeeerattttting sys$-$tem.$$

$$ Output: S $=$P$3$ph$3$ys$8$ic$6$s$is$4$$th$3$E$3$$$6$u$4$nIveR$4$s$5$e$$s$oP$2$p$3$e$5$rat$5$ing$sys$-$tem.$$

$1.$ Design an algorithm for this problem using a Divide and Conquer approach.

$($a$)$ Create a step$-$by$-$step graphical visualization $($i$.$e using diagrams$)$ of your

solution for this problem using the following string S $=$ImaaaGGinat$-$iooOn$0$n is more

imppppPP ortanNnnn t t$$ha$$n knnnnow$-$ledge$.$ Students are allowed to hand$-$drawn

their solutions for this problem.

$($b$)$create an step$-$by$-$step algorithm for this problem $($in plain english$).$ Your

algorithm must work for all the given strings S$,$ including empty strings. In addition,

your algorithm must consider all the corner cases that you may encounter in this problem.

Neither code nor pseudocode is allowed in this problem

$2.$ Pseudocode your algorithm from problem $(1)$ part $($b$).$ Note that your pseudocode

must be understood also by non$-$technical readers to get credit for this problem, and it must

be pseudocoded using the Divide and Conquer approach defined by your algorithm

$3.$ Compute the Theta time complexity of your algorithm:

$($a$)$ Show step$-$by$-$step the process to create your T $($n$)$ function from your pseudocode in problem$(2).$

$($b$)$ Use the Master Theorem to compute the Theta time complexity of your algorithm from your T $($n$)$ function. Show the process step$-$by$-$step to get credit

$($c$)$ Prove that the space complexity of your algorithm meets the constraint outlined

in the problem statement $($constant space complexity $\backslash$Theta $(1))$

$4.(1$ point$)$ Find an optimization for your algorithm $($if any$).$ That$$s it$,$ find a new approach

that will improve the actual time complexity of your algorithm. For this problem, you can use

an approach other than Divide and Conquer. First create an algorithm for your optimization,

secondly$,$ compute the time complexity for your optimization, and explain why this new

optimization is better than your original algorithm for this problem. If you are unable to

come up with an optimization for your algorithm, or you believe that it can$$t be optimized

beyond a Divide and Conquer approach, then explain which other approaches you tried to

optimize your algorithm, and why they didn$$t work.