CareerCup

Varun,

My thoughts around this is:

2 Bits: 00,01,10,11 - In this the given set is 11,00 so the longest strings would be formed using 01 or 10. So it can be 101010101010....infinite or 01010101010101...infinite.

3 Bits: 000,001,010,011,100,101,110,111 - Among these elements the given set contains 101,111,00,110.....so any longest string that you form would be with remaining elements
like 010 or 000 or 011 or 100

Is this a kind of pattern that we found that what are the possible combination of string that you can form with X no of bits and subtract the given set would give us the longest strings.

Off course this is on an assumption that the strings are formed only with 1`s and 0`s.

Best Regards,
Sai

what is the size limit on the strings that we're given?

I believe graph algorithm will be good for this.
1. Assume there are M strings in the Set
2. Assume there are N characters
3. Assume the longest string in the Set, length = K

So,
1. you can construct nodes which value of string (length <= K) and does not contains any string in the Set.
2. try to construct the (segments) of the nodes
a. it includes the self loop links
b. the longest segments (concat string length > K), stop
3. Use graph search to find the longest path in the graph
a. if you find a loop, the answer is 'infinite'
b. otherwise, the longest path is what you have.

Code not working correct for second case rite?
I copied and compiled this on my machine it I get
-1
000000
000001

Please recheck

My proposal can be devided in 2 main steps

1- From the input deduce the alphabet ( all the symbols that appear at least once in the items of the input list )
eg1 : 1ab, acg, 105, 11 ==> alphabet {1,a,b,c,0,5}
2- Using the alphabet try to generate words which lengths are equal to the maximum length of the strings ( here 3), but without any item of the input as substring. If this is not possible then the maximum length of the string will be inferior to the maximum of the input strings ( here < 3 ) otherwise continue the process to double the length of the words ( 6 )
eg2 :
1a1,1ac,1a0,1a5 etc.
then
eg 3 : 1a1 5cb

if it is possible to double the length of the word then the length will be infinite
otherwise ...

Mine solution is for binary string but it can be extent to string with a set of character. The idea based on extending feasible level of a suffix tree. The infinity condition is based on the repeat of the substring, when substring repeat we can easily construct a solution with infinite length
@Edit: change .size() to .length() to get the length of the string

#include <iostream>
#include <string>
#include <vector>

bool check_contain(std::string& a, const std::vector<std::string > subs) {
    for (int i=0; i< subs.size(); ++i) {
        if (a.length() >= subs[i].length()) {
            std::string s = a.substr(a.length() - subs[i].length(), subs[i].length());
            if (s == subs[i])
                return true;
        }
    }
    return false;
}

bool check_repeat(std::string& a, int n) {
    if (a.length() < 2 * n)
        return false;
    std::string s1 = a.substr(a.length() - n, n);
    std::string s2 = a.substr(a.length() - 2 * n, n);
    return s1.compare(s2) == 0;
}

int main(int argc, char** argv)
{
    std::string arr[] = {"11", "00"};
    //std::string arr[] = {"101", "111", "00", "110"};
    std::vector<std::string > ref(arr, arr + 2);
    int max_length = 0;
    for (int i=0; i< ref.size(); ++i)
        if (ref[i].length() > max_length)
            max_length = ref[i].length();

    std::vector<std::string > non_cover_set_prev;
    std::vector<std::string > non_cover_set;

    non_cover_set_prev.push_back(std::string(""));

    bool repeat = false;
    while (!repeat) {
        non_cover_set.clear();
        for (int i=0; i< non_cover_set_prev.size() && !repeat; ++i) {
            std::string a0 = non_cover_set_prev[i] + '0';
            std::string a1 = non_cover_set_prev[i] + '1';
            if (!check_contain(a0, ref)) {
                non_cover_set.push_back(a0);
                repeat = repeat || check_repeat(a0, max_length);
            }
            if (!check_contain(a1, ref)) {
                non_cover_set.push_back(a1);
                repeat = repeat || check_repeat(a1, max_length);
            }
        }

        if (non_cover_set.size() == 0)
            break;
        non_cover_set.swap(non_cover_set_prev);
    }

    if (repeat) {
        std::cout << -1 << std::endl;
    }
    for (int i=0; i< non_cover_set_prev.size(); ++i) {
        std::cout << non_cover_set_prev[i]  << std::endl;
    }
    return 0;
}