Question:
Design a class newString such that the time complexity for insertion, deletion and read is less than o(n).

class NewString{
public:
char read(int index);
void insert(char c, int index);
void delete(int index);
}

Any idea on how to do this?