Amazon developers are creating a new security module for Amazon Web Services. One of its functions is to obfuscate incoming messages. The obfuscation method is to select some substring of the message and right rotate that substring by 1 position one time only. The substring is selected in such a way that the resulting obfuscated message is alphabetically the smallest message that can be formed using this operation.
Here, right rotating any string by 1 position is to shift every character of string a in the right direction by 1 position and remove the last character and append it to the beginning of string a. For example, a = "ahssd", after right rotation by 1 position string a changes to "dahss".
Given the input message as a string, find the obfuscated message.
Note: A string x is alphabetically smaller than string y, if either x is a prefix of y (and x ≠y), or there exists such i (0 ≤ i < min(|x|, |y|)), that x[i] < y[i], and for any j (0 ≤ j < i) x[j] = y[j]. Here, |a| denotes the length of the string a.
Function Description
Complete the function findObfuscateMessage in the editor below.
findObfuscateMessage has the following parameter:
- string message: the input message
Returns
string: the encrypted message
Image source will be attached in next update...
Example 1:
Input: message = "aahhab"
Output: "aaahhb"
Explanation:These are some of the possible strings.
Rotating the substring "hha" produces "ahh". Replace "hha" in the original string to get "aaahhb", the alphabetically smallest message that can be formed. Return "aaahhb".
- 1 ≤ |message| ≤ 10^5
- The string message contains only lower case English letters.
input:
output: