Given two strings, find the longest common bag of chars

Question

This question is slightly different from the kind of finding longest sequence or substring from two strings.

Given two string of the same size N, find the longest substrings from each string such that the substrings contains the same bag of chars.

The two substrings may not necessarily have the same sequence. But they must have the same bag of chars.

For example,

a = ABCDDEGF b = FPCDBDAX

The longest matching bag of chars are ABCDD (ABCDD from a, CDBDA from b)

How to solve this problem?

---

UPDATE

The goal is to find substrings from each input string, such that they have the same bag of chars. By saying "substring", they must be consecutive chars.

---

Update: Initially I thought of a dynamic programming approach. It works as below.

To compare two bags of chars of the same length K, it would take O(K) time to achieve so. Convert each string into a shorten form:

ABCDDEGF -> A1B1C1D2E1G1F1
FPCDBDAX -> A1B1C1D2F1P1X1

The shorten form is sorted alphabets followed by number of frequencies in the string. Construct, sort, and compare the shorten forms would take O(K) time in total. (Implementation can be achieved by using an array of chars though)

Two bags of chars are equal iif their shorten forms have the same chars and respective frequencies.

In addition, it takes O(logK) time to find the difference chars between the two string.

Now, for two input strings:

1. If their shorten forms are identical, then this is the longest common bag of chars.
2. Find chars in string1 such that they do not appear in string2. Tokenize string1 into several substrings based on those chars.
3. Find chars in string2 such that they do not appear in string1. Tokenize string2 into several substrings based on those chars.
4. Now, we have two list of strings. Compare each pair (which in turn is the same problem with a smaller size of input) and find the longest common bag of chars.

The worst case would be O(N³), and best case would be O(N). Any better idea?

Answer 1

Create a set of the characters present in a, and another of the characters present in b. Walk through each string and strike (e.g., overwrite with some otherwise impossible value) all the characters not in the set from the other string. Find the longest string remaining in each (i.e., longest string of only "unstruck" characters).

Edit: Here's a solution that works roughly as noted above, but in a rather language-specific fashion (using C++ locales/facets):

#include <string>
#include <vector>
#include <iostream>
#include <locale>
#include <sstream>
#include <memory>

struct filter : std::ctype<char> {
    filter(std::string const &a) : std::ctype<char>(table, false) {
        std::fill_n(table, std::ctype<char>::table_size, std::ctype_base::space);

        for (size_t i=0; i<a.size(); i++) 
            table[(unsigned char)a[i]] = std::ctype_base::upper;
    }
private:
    std::ctype_base::mask table[std::ctype<char>::table_size];
};

std::string get_longest(std::string const &input, std::string const &f) { 
    std::istringstream in(input);
    filter *filt = new filter(f);

    in.imbue(std::locale(std::locale(), filt));

    std::string temp, longest;

    while (in >> temp)
        if (temp.size() > longest.size())
            longest = temp;
    delete filt;
    return longest;
}

int main() { 
    std::string a = "ABCDDEGF",  b = "FPCDBDAX";
    std::cout << "A longest: " << get_longest(a, b) << "\n";
    std::cout << "B longest: " << get_longest(b, a) << "\n";
    return 0;
}

Edit2: I believe this implementation is O(N) in all cases (one traversal of each string). That's based on std::ctype<char> using a table for lookups, which is O(1). With a hash table, lookups would also have O(1) expected complexity, but O(N) worst case, so overall complexity would be O(N) expected, but O(N²) worst case. With a set based on a balanced tree, you'd get O(N lg N) overall.

Answer 2

Just a note to say that this problem will not admit a "greedy" solution in which successively larger bags are constructed by extending existing feasible bags one element at a time. The reason is that even if a length-k feasible bag exists, there need not be any feasible bag of length (k-1), as the following counterexample shows:

ABCD
CDAB

Clearly there is a length-4 bag (A:1, B:1, C:1, D:1) shared by the two strings, but there is no shared length-3 bag. This suggests to me that the problem may be quite hard.