Robert Eisele
Engineer, Systems Architect and DBA

Skillvalue: Find the Link

Given a set of strings, find the longest common subtring. It is assumed that the input set of strings will never have more than one substring in common.

Input: file containing a vector of strings on each line.
Output: a string representing the common string. If the strings have no common substring, the output should be 0.



The output is che (common sub-sequences are not considered valid outputs; that is, ch and he in the given example, are not considered valid outputs).


Given only two strings, a very fast dynamic programming approach is known, which solves the problem in \(O(\ell^2)\), where \(\ell\) is the length of the longest string. Generalizing the problem to a finite set of strings with cardinality \(m\) is a little harder since remembering every valid path would require a tensor and filling it would lead to a complexity of \(O(\ell^m)\). A faster and more intuitive way of solving this problem is using a suffix-tree as well as a bit vector.

When we insert every suffix of a given string into a tree, like "orchestra", "rchestra", "chestra", ... "a" and mark every node as touched by the kth word, using a bit vector, we can start at the root node and check for the longest path for which all bits are set. Creating the tree can be done in \(O(m\cdot \ell^2)\). We avoid the higher computational complexity by storing every combination in the tree and therefore going into space complexity. Since we expect \(\ell<32\) we can use an integer as the bit vector and don't need to use an infinity bit set implementation like BitSet.js.

function insert(T, str, start, iter) {

  for (var i = start; i < str.length; i++) {
    var c = str[i];

    if (T[c] === undefined) {
      T[c] = {next: {}, mask: 1 << iter};
    } else {
      T[c].mask|= 1 << iter;
    T = T[c].next;

var arr = ["orchestra", "check", "chelsea"];
var T = {};
for (var k = 0; k < arr.length; k++) {
  var str = arr[k];
  for (var i = 0; i < str.length; i++) {
    insert(T, str, i, k);

Having the filled tree allows us to search for all valid substrings and extract the longest:

function findLCS(T, goal) {

  var ret = [];
  for (var k in T) {
    if (T[k].mask == goal) {
      ret.push(k + findLCS(T[k].next, goal));
  return ret;
var ret = findLCS(T, Math.pow(2, arr.length) - 1);
if (ret.length === 0) {
} else {
  console.log(ret.reduce((a, b) => a.length > b.length ? a : b))

« Back to problem overview