Question 1:

In this question, we will suggest a data structure for storing strings with a lot of

repetitions of successive characters.

We will represent such strings as a linked list, where each maximal sequence of the

same character in consecutive positions, will be stored as a single tuple containing

the character and its count.

For example, the string "aaaaabbbaaac" will be represented as the following list:

header

trailer

HIL

('a', 5)

('b', 3)

Complete the definition of the following CompactString class:

class CompactString:

def

def

def

('a', 3)

('c', 1)

_init__(self, orig_str):

"Initializes a CompactString object

representing the string given in orig str'''

1t (self, other):

add (self, other) :

Creates and returns a CompactString object that

represent the concatenation of self and other,

also of type CompactString '''