You are given a sequence of letters a and b of length n, represented as an array , where each element is either a or b. We call a segment , where , beautiful if the number of "a"s and the number of "b"s in the sub-array are equal. The length of the segment is j - i + 1, the number of elements in corresponding sub-array.

First let the arraay contain the sequence (of length 12)

a) Find all beautiful segments of length 4

b) Prove that there are no beautiful segments of length 5

c) What is the maximal length of a beautiful segment for this sequence? Justify your answer

You will now design algorithms for determining the maximal length of a beautiful segment, when the array os given as input

d) How many segments (not necessarily beautiful), as a function of n, are there in total for a sequence of length n? Describe an algorithm that, given a sequence of length n, determines the maximal length of a beautiful segment for this sequence.

e) Describe for every , an example sequence of "a"s and "b"s of length n that has beautiful segments. Justify your answer.

f) suppose you want to check which of the initial segments , for are beautiful. Describe an algorithm that completes this task in linear time. You algorithm may need to compute, for each i , some auxiliary information in order to do this.

g) Based on the previously computed auxiliary information, formulate and prove a statement of the following form: "A segment is beautiful if and only if..." Using the chracterization, design a linear-time algorithm that, given a sequence of length n, determines the maximal length of a beautiful segment for this sequence. Justify the correctness of the algorithm and prove that it runs in linear time