You are given a message string S consisting of lowercase English alphabet letters. "ada" is a noise word and all the words that can be formed by adding “da” any number of times at the end of any noise word is also considered as a noise word. For example, the words “adada”, “adadadadada”, ”adada” are noise words but “dada”, ”ad”, ”aad” are not considered noise words.
You have to move all the noise words present in the message signal to the end of the message (in the same order as they occur in the message S) so that the filter can truncate the noise from the end.
Example 1:
Input:
S = "heyadadahiadahi"
Output: "heyhihiadadaada"
Explanation: ”adada” and “ada” are the
noise words. Noises are moved to the end
in the same order as they appear in the
string S.
Example 2:
Input:
S = "heyheyhello"
Output: "heyheyhello"
Explanation: There is no noise in the signal.
Your Task:
You need not take any input or print anything. Your task is to complete the function updateString() which takes string S as input parameter and returns the message string with noise words at the end.
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(|S|).
Constraints:
1 ≤ length (string) ≤ 10^5

见题面

见题面