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:

If their shorten forms are identical, then this is the longest common bag of chars.
Find chars in string1 such that they do not appear in string2. Tokenize string1 into several substrings based on those chars.
Find chars in string2 such that they do not appear in string1. Tokenize string2 into several substrings based on those chars.
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?

It looks like you're using count sort for the "shorten form" - you can only use it if you know the range of your characters. Next, you aren't really using the count, only as a way of checking what characters are present. As for point 4 - it isn't a smaller problem input. Given abbbbbb and aaaaaaaaab, you cannot eliminate any letter. Further, the count of the characters gives you very little information, especially when you don't know K from the start. — Kobi
@Kobi: Chars are ranged integers. For example, ASCII would be in range 0 - 128. It will be more tricky to allow Unicode chars. We need the frequency count to test "equality" the two shorten forms. — SiLent SoNG
I'm sorry - isn't it ab, or am I not understanding the question? — Kobi
@Kobi: Initially the two input strings have the same length. It is possible that after tokenization we will face two strings of different length... you are right. I am thinking a solution to your question. — SiLent SoNG

Jerry Coffin Jerry Coffin · Accepted Answer · 2010-08-21T05:14:47

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.

Given two strings, find the longest common bag of chars

4 Answers