Lexicographically Smallest Encoded String - Rippling Online Assessment IIT BHU

Problem Preview

"You are given a string originalString consisting of lowercase English letters. Initially, two empty strings are available: temporaryString encodedString You may perform the following operations any number of times until originalString and temporaryString are both empty. Operation 1 Remove the first character of originalString and append it to the end of temporaryString. Operation 2 Remove the last character of temporaryString and append it to the end of encodedString. At any step, you may perform either operation whenever it is valid. Your task is to determine the lexicographically smallest possible encodedString that can be obtained after processing all characters. Notes temporaryString behaves like a stack. Every character from originalString must appear exactly once in encodedString. A valid sequence of operations must eventually empty both originalString and temporaryString. Function Signature string smallestEncodedString(string originalString); Input A single string originalString. Output Return the lexicographically smallest possible encodedString. Constraints 1 ≤ |originalString| ≤ 2 × 10^5 originalString contains only lowercase English letters ('a'–'z'). Example 1 Input bac Output abc Explanation One optimal sequence of operations is: original: bac temp: "" encoded: "" Move 'b' to temp. temp = "b" Move 'a' to temp. temp = "ba" Move 'a' from temp to encoded. encoded = "a" Move 'b' from temp to encoded. encoded = "ab" Move 'c' to temp. temp = "c" Move 'c' from temp to encoded. encoded = "abc" No other valid sequence produces a lexicographically smaller string. Example 2 Input zza Output azz" Explanation By delaying the removal of the two 'z' characters until after 'a' has been moved to temporaryString, the smallest possible encoded string is "azz"."