Alex Stone - 2 months ago 10
C++ Question

# Finding Lexicographically smallest arrangement of some string

The Title might seem as if it is a very common question but please bear with me.

Basically lets say at each index of the string you know which alphabets could be in that index, and then you want to find lexicographically smallest arrangement.

So for example:

``````Index  |  Options
-------|----------
1    |  'b'
2    |  'c', 'a'
3    |  'd', 'c'
4    |  'c', 'a'
``````

So hence, o/p should be
`badc`
. And yes btw, characters cannot repeat so no greedy algorithm.

I think we could use some sort of Breadth First Search by creating a queue or something of the string and each time we found we could not create another permutation, you pop that out of the list. Doubt this is optimal though, must be something in
`O(N)`
. Any ideas?

And no, I don't think C is bad, but I would prefer code snippets in C/C++ :p

Thanks!

This can be solved by matching algorithm. You can use a network flow solution to solve this. This can be broken down into a bi-partite graph problem.

To be precise maximum weight assignment problem or maximum cost maximum matching would be a solution.

Below is the bipartite set of vertices -

``````LEVEL          Alphabets
1                 a
2                 b
3                 c
4                 d
e
.
.
.
z
``````

Now assign edges from set Level to set Alphabet, only and only if those are the options for that level. So these will be edges here - {1,b} , {2,a}, {2,c} , {3,c} , {3,d} ,{4,a} ,{4,c} Now, to get the lexicographically least result you need to assign weight to the edges in this fashion -

``````Edge Wt. = 26^(N-Level) * ('z' - Alphabet)
``````

So for example edge weight for edge {2,c} would be

``````26^(4-2) * (26-3) =  26^2*23
``````

Now you can use a standard maximum cost maximum matching solution. Which is a polynomial solution. And this would be the best approach as far as I can think now. The naive solution is an exponential solution 26^N, so I think you would be happy with a polynomial solution.