Problem Link: https://onlinejudge.org/external/2/200.pdf

Note: I think the problem statement was very much unclear. The important thing to notice is that it is explicitly mentioned in the input section that the string will be ordered. So you cannot change the order of the string.

Now, the problem actually demands printing unique characters column wise maintaining that each character you are printing cannot be printed twice. So simply put – “print unique characters of the ordered strings by column-wise traversal”.

For example, for the input:

XYZ

ZUX

XWV

#

So in the 1st column, there are XZX, where X is repeated, so we get XZ from this column.

in the 2nd column, there is YUW, where no character was found before, all are new, so we get YUW from this column.

In the 3rd column, there are ZXZ, here both X and Z already exist in our finding, only V is new, so we get V from this column.

At the end of the traversal, by concatenating all column’s results, we have XZYUWV – which is the output.

I have solved this using the above brute force method, so no DFS or Topological Sort is needed here if time is a concern.

**We’ll have to keep in mind that, all string sizes may not be the same. So we’ll have to take care of that while traversing and accessing elements.

**For the first time, the output of UDebug’s test cases’ output didn’t match up with mine (but this code was accepted by the UVa) which means that the UDebug test cases are wrong because the output was supposed to be unique as per my understanding. If that is not the case not, please let me know in the comments. Thanks!

Code:

#include <bits/stdc++.h>

using namespace std;

int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);

    vector<string> v;
    int maxi=INT_MIN;
    string s;
    while(cin>>s)
    {
        if(s!="#")
        {
            v.push_back(s);
            maxi=(maxi, s.size());
        }
        else
        {
            unordered_map<char,int> visited;
            for(int j=0; j<maxi; j++)
            {
                for(int i=0; i<v.size(); i++)
                {
                    string ss=v[i];
                    if(j<ss.size() && !visited.count(ss[j]))
                    {
                        cout<<ss[j];
                        visited[ss[j]]=1;
                    }
                }
            }
            cout<<endl;
            v.clear();
            maxi=INT_MIN;
        }
    }
    return 0;
}