https://cses.fi/problemset/task/1113 I was solving this problem from cses , I came up with an idea which is I can know the first ans last character of each string in the lexicographical sorted rotations which is.

The last characters is the input itself and the first characters is the sorted input

For example: (* represents an unknown character)

s = "cb#ab"

Then the lexicographical sorted rotations from the input are:

"****c"

"****b"

"****#"

"****a"

"****b"

And the sorted input is:

"#abbc"

So the first characters are:

"#****"

"a****"

"b****"

"b****"

"c****"

By combining i will have:

"#***c"

"a***b"

"b***#"

"b***a"

"c****b"

Basically I will construct a graph by adding a directed edge from first to last character of each string. The graph idea if x have a direct edge to y then y is before x in the answer string. So I can just find an Euler circuit which starts at '#' and ends at '#' and it will be the answer. But the problem with the idea is if there is a character which appears more than once. The logic may break because then you will have more than one choice to choose. But actually there should be a unique answer (all the choices are wrong except one but idk how to differentiate between them)

Any ideas to improve the answer or any other ideas to solve the problem ?

Thanks in advance :)

edit : solved :)

edit: my AC solution

I knew the solution but it was just an intuition i still don't have a proof, But that's it

You just have to number the strings like if you have string s = "aab#a"

every "a" should have something to differentiate from others so I numbered them

so the string will be a1 a2 b1 # a3

also the sorted string the same

sorted = "#aaab" so it will be # a1 a2 a3 b1

so overall it's

"# *** a1" "a1 *** a2" "a2 *** b1" "a3 *** #" "b1 *** a3"

then the graph is

'# -> a1 -> a2 -> b1 -> a3 -> #

then the answer is a1 a2 b1 a3 which is "aaba"

and that's it :)