Alex Stone - 8 months ago 43

C++ Question

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`

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)`

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

Thanks!

Answer

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.