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.
Example 1:
Input: S = "ababcababcd"
Output: abcd
Explanation: We can encrypt the string
in following way : "ababcababcd" ->
"ababcd" -> "abcd"
Example 2:
Input: S = "zzzzzzz"
Output: zzz
Explanation: The string can be encrypted
in 2 ways: "zzz" and "zzzz". Out of
the two "zz*z" is smaller in length.
Your Task:
You don't need to read input or print anything. Complete the function secretCipher() which takes the message string S as input parameter and returns the shortest possible encrypted string.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ |S| ≤ 10^{5}

见题面

见题面