ReversingBracketsSort | Topcoder Archive

Problem Statement

There is a really unsafe way to write encrypted messages that works as follows: Some parts of the original sentence are reversed and enclosed in brackets so the reader will know how to unencrypt the message.

For example, the string "[o[ell]h][dlrow]" is one possible way to encrypt the string "helloworld". Note that brackets can be nested. Nesting is interpreted in the same way that nested parentheses are normally interpreted. In this example, the substring "ell" gets reversed twice because it is inside 2 pairs of brackets. Brackets must always be properly matched.

You will be given a String s, and you must encrypt s in such a way that the letters are in alphabetical order. Return the shortest such string. If there are multiple solutions, return the one among them that comes earliest lexicographically. If there is no possible solution, return the empty string.

Definition

Class:: ReversingBracketsSort
Method:: reverseSort
Parameters:: String
Returns:: String
Method signature:: String reverseSort(String s)
(be sure your method is public)

Notes

If two strings have the same size, the one that comes earlier lexicographically is the one with the lower ASCII value in the first position at which they differ.
The possible output characters ordered with increasing ASCII value are: '[', then ']' and then all lowercase letters in alphabetic order.

Constraints

s will have between 1 and 50 characters, inclusive.
Each character of s will be a lowercase letter ('a'-'z').

Examples

```
"badecf"
```
```
Returns: "[ab][c[de]]f"
```
Remember that you can nest brackets.
```
"cadb"
```
```
Returns: ""
```
Since brackets must properly match, you can't make 'b' go before 'c' without surrounding the whole expression with brackets. Then you have [bdac]. To send 'a' to the beginning of the expression, you have to use a second bracket set this way (because no bigger bracket set will move 'a'): [[adb]c]. And now it is impossible to send 'd' to the end.
```
"abcdef"
```
```
Returns: "abcdef"
```
No brackets needed here.
```
"zyx"
```
```
Returns: "[xyz]"
```
One set of brackets is enough.

"baabaaababababaeeecccdccdcdcdc"

Returns: "[a[aa[a[aaa[a[ab]b]b]b]b]b][c[ccc[c[cc[cd]d]d]d]eee]"

Watch out for repeated letters!

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.