Help to identify best optimum algorithm : challenge of keyboard

Question

Hi

Below is my code which seems to be having opportunity to optimise:

https://code.sololearn.com/caMGiSUHU4l9/?ref=app

Problem statement is described as code comment and it's working as expected... Only concern is that I am not able to pass all the test cases due to time limit exceeded... Sole purpose of this post is to learn effective algorithm... So, I am not looking for your code but asking for help on what could be done on this code to make it more optimised...

Answer 1

Just coming up with something on the spot here but, since there is only a '<' which goes all the way to the beginning and a '>' that goes all the way to the end, that means you never have to insert something in the center, you only append to either the front or the back.
That sounds like a perfect task for a deque which can do exactly that efficiently.
https://en.cppreference.com/w/cpp/container/deque

But what exactly should be the type of deque? Not char, because if you encounter the '#' character then you have to erase from the deque and you end up moving things around in the thing again.

A better type would be std::string, you can easily remove 1 character from the back of it pretty much free of charge and you can append characters easily as well.
You also never have to insert anything new into it either, instead you just push an entire new string to the front.

This way you never have to delete from the middle of the string and therefore avoid an expensive move around of the elements.

After all that you simply iterate through the deque and print every string.

Since you didn't ask for code I won't include an example. But if you change your mind, I'll post what I mean with some code. :)

P.S. I'm pretty sure you switched '*' and *#' around

Answer 2

Ketan Lalcheta I implemented it myself and it works for me.
std::string has a pop_back function that works for the '*' and it does not matter if the string ends up empty.
Of course you'll have to track the index for the deque yourself.

myse<l*f>a
Would create a deque like
"f" <-- this would contain "lf" if there was no '*'
"myse"
"a"

Answer 3

Here you go, there are still a few optimizations you could perform, like reusing empty strings. Also I didn't implement the numlock part because I was lazy. There may be some more bugs, I didn't run the test cases. :P

https://code.sololearn.com/cAmhZD86BB58/?ref=app

Answer 4

Np, I updated the comment in the code because I messed that up. :)

Answer 5

np, it does have alot of space cost though if there are alot of delete operations because you can't simply remove the empty strings in the middle of the deque so there is a chance that you end up with alot of empty strings in the middle.
There is always a cost somewhere sadly :(

Answer 6

Hi Dennis , thanks....

True... Deque with char will not solve the purpose because he<lo would ask us to insert 'o' neither at end nor at beginning

If I m not wrong in understanding the same, you mean to say that push string into front of deque.... But how to remove char from last is not clear....

For example, my input is myself* and you have at last myself into first of Deque but now * is asking to delete last char and provide output as mysel but how to get it... Front of Deque doesnot solve purpose.....

Another issue is input myse<l*f>a as after * we have to delete l which was inserted at front of string

Answer 7

Yup... I messed * and # in comment section and updated it now as per code :)

Answer 8

I tried to go with two bool and string as data type in same code but no success.... Could you please share yours ?

Answer 9

Cool... It must be a help.... Bug and pending parts I would take care later... Just wanted a flow and that's what you have provided ...
Many thanks for the help and your efforts.

Answer 10

Hi , I have a query:

You had a piece of code in else as below :

d[deqIndex] += c;

As deque is for string type , index of Deque means LHS of above is string.... Does this not mean we are doing operation on string itself ?

With this , can we directly add character to string directly as c is character type...

Answer 11

Yes, that piece of code adds a character to the string contained in the deque.

In this case it kinda acts as an insertion into the middle of the string if the deque wasn't there.

ab<cd

In this code would go like:

Start out with a deque with 1 empty string inside it.
Push 'a' to the back of the string at index 0.
Push 'b' to the back of the string at index 0.
'<' causes a new string to be inserted at the beginning.
Push 'c' to the back of the (new) string at index 0.
Push 'd' to the back of the (new) string at index 0.

And you'll see that we basically did this with just 1 string, if we didn't use a deque:
Push 'a' to the back of the string.
Push 'b' to the back of the string.
Insert 'c' at the first index of the string.
Insert 'd' at the second index of the string.

Answer 12

Wow..... Never thought of such a useful Deque is...

Now I think I got it.... Avoiding costly copy operation of existing char to insert char in between string ....

Now having deque which has string elements equals to number of < plus number of > plus one (due to initial entries)

Within each string at max adding content at the end of string...

Simply wow.... !

Appreciate your patience, effort and extended hand of help to make me understand this....