I am not able to understand how to do this problem. Hints/solution would be appreciated. The problem has a tag of stack if it helps.

Geek wants to send an encrypted message in the form of string S to his friend Keeg along with instructions on how to decipher the message. To decipher the message, his friend needs to iterate over the message string from left to right, if he finds a β*β, he must remove it and add all the letters read so far to the string. He must keep on doing this till he gets rid of all the β*β.
Can you help Geek encrypt his message string S?

Note: If the string can be encrypted in multiple ways, find the smallest encrypted string.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Constraints:
1 β€ |S| β€ 10^5

Input : mnmmnmnmmnmnmmnmnmmnmnm
Output: mnmmn**mnm

Input : hxhxhxhxhxhxhxhxhxhxhxhxhxhxhxhx
Output: hx****

They are correct. We have to do encryption of the string.

Can you send the link to the question .

1 Like

The problem is available only for a day. I have copy-pasted the statement, constraint and examples.

I am not sure about the exact answer , but the approach which comes into my mind is to calculate the prefix function and then just put each index into while loop until the value of prefix function becomes 1 and also maintain a visited array so that you donβt need to compute the values once computed again . Like we do in KMP (Knuth Morris Pratt Algorithm). Well if you are really a 2 Star then I will suggest you to not get into these intermediate Algorithm and first focus on the beginner Data Structure and Algorithm and building critical thinking . ( This is just a free suggestion you can ignore it if you want )

Hey! Can you please elaborate ??