Take the 2-minute tour ×

This is a challenge to come up with the most elegant JavaScript, Ruby or other solution to a relatively trivial problem.

This problem is a more specific case of the Longest common substring problem. I need to only find the longest common starting substring in an array. This greatly simplifies the problem.

For example, the longest substring in [interspecies, interstelar, interstate] is "inters". However, I don't need to find "ific" in [specifics, terrific].

I've solved the problem by quickly coding up a solution in JavaScript as a part of my answer about shell-like tab-completion (test page here). Here is that solution, slightly tweaked:

function common_substring(data) {
  var i, ch, memo, idx = 0
  do {
    memo = null
      ch = data[i].charAt(idx)
      if (!ch) break
      if (!memo) memo = ch
      else if (ch != memo) break
  } while (i == data.length && idx < data.length && ++idx)

  return (data[0] || '').slice(0, idx)

This code is available in this Gist along with a similar solution in Ruby. You can clone the gist as a git repo to try it out:

$ git clone git://gist.github.com/257891.git substring-challenge

I'm not very happy with those solutions. I have a feeling they might be solved with more elegance and less execution complexity—that's why I'm posting this challenge.

I'm going to accept as an answer the solution I find the most elegant or concise. Here is for instance a crazy Ruby hack I come up with—defining the & operator on String:

# works with Ruby 1.8.7 and above
class String
  def &(other)
    difference = other.to_str.each_char.with_index.find { |ch, idx|
      self[idx].nil? or ch != self[idx].chr
    difference ? self[0, difference.last] : self

class Array
  def common_substring
    self.inject(nil) { |memo, str| memo.nil? ? str : memo & str }.to_s

Solutions in JavaScript or Ruby are preferred, but you can show off clever solution in other languages as long as you explain what's going on. Only code from standard library please.

Update: my favorite solutions

I've chosen the JavaScript sorting solution by kennebec as the "answer" because it struck me as both unexpected and genius. If we disregard the complexity of actual sorting (let's imagine it's infinitely optimized by the language implementation), the complexity of the solution is just comparing two strings.

Other great solutions:

Thanks for participating! As you can see from the comments, I learned a lot (even about Ruby).

share|improve this question
Note: this isn't code golf. –  mislav Dec 16 '09 at 23:33
The accepted answer demonstrates a really cool solution. Well, of course, the answer itself is broken, but who cares, the idea is so cool ;) –  Alexis Jul 25 '13 at 8:31
add comment

27 Answers

up vote 36 down vote accepted

It's a matter of taste, but this is a simple javascript version: It sorts the array, and then looks just at the first and last items.

function sharedStart(array){
    var A= array.slice(0).sort(), 
    word1= A[0], word2= A[A.length-1], 
    L= word1.length, i= 0;
    while(i<L && word1.charAt(i)=== word2.charAt(i)) i++;
    return word1.substring(0, i);


sharedStart(['interspecies', 'interstelar', 'interstate'])  //=> 'inters'
sharedStart(['throne', 'throne'])                           //=> 'throne'
sharedStart(['throne', 'dungeon'])                          //=> ''
sharedStart(['cheese'])                                     //=> 'cheese'
sharedStart([])                                             //=> ''
sharedStart(['prefix', 'suffix'])                           //=> ''
share|improve this answer
Wow. This blew me away –  mislav Dec 16 '09 at 23:43
Note that sorting is done in O(n·log n). –  Gumbo Dec 19 '09 at 17:51
I would upvote this more than once if I could. Really nice. –  twk Mar 15 '10 at 17:28
You don't have to sort it. Right? Just find the smallest one and the largest one and compare the two. –  Kai Sep 16 '12 at 17:07
This doesn't work if the array has one item or is all duplicates. –  Jeff May Dec 26 '13 at 1:40
show 2 more comments

In Python:

>>> from os.path import commonprefix
>>> commonprefix('interspecies interstelar interstate'.split())
share|improve this answer
Can't believe it. Python has this in stdlib? –  mislav Dec 16 '09 at 23:27
Yes, but it's hidden in the os.path module, although it is a string manipulation function useful. –  Roberto Bonvallet Dec 17 '09 at 0:08
Good job, python. Feels like cheating. –  Ray Aug 14 '12 at 16:35
add comment

Ruby one-liner:

l=strings.inject{|l,s| l=l.chop while l!=s[0...l.length];l}
share|improve this answer
This traverses each string once for each character not in the result. Not very efficient. –  Svante Dec 16 '09 at 20:26
It might need more iterations than other solutions, but I like it. It's what I consider elegant. –  mislav Dec 16 '09 at 23:32
add comment

You just need to traverse all strings until they differ, then take the substring up to this point.


loop for i upfrom 0
     while all strings[i] are equal
     finally return substring[0..i]

Common Lisp:

(defun longest-common-starting-substring (&rest strings)
  (loop for i from 0 below (apply #'min (mapcar #'length strings))
     while (apply #'char=
                  (mapcar (lambda (string) (aref string i))
     finally (return (subseq (first strings) 0 i))))
share|improve this answer
+1, this is the optimal solution –  MAK Dec 16 '09 at 21:00
+1 for lisp! good stuff –  André Terra Sep 29 '11 at 21:41
Isn't it more optimal to do a first pass to find the minmax of available options, in order to reduce the search tree? –  Denis Nov 28 '13 at 18:18
@Denis: 1. There is no "more optimal". The optimum is the optimum. There are two optimizations possible in the given Lisp implementation: replace both apply forms with loops or dos (also eliminating the mapcar), and break off in the second one as soon as a mismatch occurs. 2. What is the "minmax of available options" here? 3. There is no search tree here. If the length of the correct result is n, you need to have looked at each character before index n in each input substring. That is what this routine does, and it looks at each character exactly once, linearly. –  Svante Nov 29 '13 at 20:27
add comment

My Haskell one-liner:

import Data.List

commonPre :: [String] -> String
commonPre = map head . takeWhile (\(x:xs)-> all (==x) xs) . transpose

EDIT: barkmadley gave a good explanation of the code below. I'd also add that haskell uses lazy evaluation, so we can be lazy about our use of transpose; it will only transpose our lists as far as necessary to find the end of the common prefix.

share|improve this answer
This looks like very nice code! Can you take a moment to explain it a bit to us who don't know the language? (You don't have to go to large depths) –  mislav Dec 16 '09 at 23:47
first you transpose the strings. ["abc","abd","aed"] -> ["aaa","bbe","cdd"], then you take from this list until something differs ["aaa"] and then you take the first element of each list in this list (strings are just lists in Haskell) which gets you "a". it's easier to read from right to left, because that is the way that data travels in Haskell's point free style. –  barkmadley Dec 17 '09 at 5:49
Lovely code, but unfortunately this fails when a string is a prefix of another, e.g. commonPre ["foo", "foobar", "foobarbaz"] == "foobarbaz". –  Nefrubyr Dec 13 '10 at 16:50
add comment

Yet another way to do it: use regex greed.

words = %w(interspecies interstelar interstate)
j = '='
str = ['', *words].join(j)
re = "[^#{j}]*"

str =~ /\A
    (?: #{j} ( #{re} ) #{re} )
    (?: #{j}    \1     #{re} )*

p $1

And the one-liner, courtesy of mislav (50 characters):

p ARGV.join(' ').match(/^(\w*)\w*(?: \1\w*)*$/)[1]
share|improve this answer
Nice! A one-line version of this would be words.join(" ").match(/^(\w*)\w*(?: \1\w*)*$/)[1]. Note: the regexp would have to be updated slightly to make this work when matching strings that have spaces in them. –  mislav Dec 18 '09 at 11:41
add comment

In Python I wouldn't use anything but the existing commonprefix function I showed in another answer, but I couldn't help to reinvent the wheel :P. This is my iterator-based approach:

>>> a = 'interspecies interstelar interstate'.split()
>>> from itertools import takewhile, chain, izip as zip, imap as map
>>> ''.join(chain(*takewhile(lambda s: len(s) == 1, map(set, zip(*a)))))

Edit: Explanation of how this works.

zip generates tuples of elements taking one of each item of a at a time:

In [6]: list(zip(*a))  # here I use list() to expand the iterator
[('i', 'i', 'i'),
 ('n', 'n', 'n'),
 ('t', 't', 't'),
 ('e', 'e', 'e'),
 ('r', 'r', 'r'),
 ('s', 's', 's'),
 ('p', 't', 't'),
 ('e', 'e', 'a'),
 ('c', 'l', 't'),
 ('i', 'a', 'e')]

By mapping set over these items, I get a series of unique letters:

In [7]: list(map(set, _))  # _ means the result of the last statement above
 set(['p', 't']),
 set(['a', 'e']),
 set(['c', 'l', 't']),
 set(['a', 'e', 'i'])]

takewhile(predicate, items) takes elements from this while the predicate is True; in this particular case, when the sets have one element, i.e. all the words have the same letter at that position:

In [8]: list(takewhile(lambda s: len(s) == 1, _))

At this point we have an iterable of sets, each containing one letter of the prefix we were looking for. To construct the string, we chain them into a single iterable, from which we get the letters to join into the final string.

The magic of using iterators is that all items are generated on demand, so when takewhile stops asking for items, the zipping stops at that point and no unnecessary work is done. Each function call in my one-liner has a implicit for and an implicit break.

share|improve this answer
Could you decompose the solution and elaborate a bit on iterators used? –  mislav Dec 17 '09 at 0:02
Gladly. There it is :) –  Roberto Bonvallet Dec 17 '09 at 0:29
why "izip" and "imap"? at first thought it could be that they are case-insensitive, but then I realized that doesn't make much sense –  mislav Dec 17 '09 at 9:46
It reminds me of Haskell. Really functional style python code. –  Ray Aug 14 '12 at 16:56
Learning Haskell has certainly affected my Python :) –  Roberto Bonvallet Aug 15 '12 at 23:16
show 1 more comment

This is probably not the most concise solution (depends if you already have a library for this), but one elegant method is to use a trie. I use tries for implementing tab completion in my Scheme interpreter:


For example:

tree = Trie.new
%w[interspecies interstelar interstate].each { |s| tree[s] = true }
#=> "inters"

I also use them for matching channel names with wildcards for the Bayeux protocol; see these:



share|improve this answer
You don't need a trie. As soon as any branch would occur, you're done anyway. –  Svante Dec 16 '09 at 19:03
Really interesting—thanks for sharing! –  mislav Dec 17 '09 at 0:00
add comment

Just for the fun of it, here's a version written in (SWI-)PROLOG:

common_pre([[C|Cs]|Ss], [C|Res]) :-
  maplist(head_tail(C), [[C|Cs]|Ss], RemSs), !,
  common_pre(RemSs, Res).
common_pre(_, []).

head_tail(H, [H|T], T).


?- S=["interspecies", "interstelar", "interstate"], common_pre(S, CP), string_to_list(CPString, CP).


CP = [105, 110, 116, 101, 114, 115],
CPString = "inters".


(SWI-)PROLOG treats strings as lists of character codes (numbers). All the predicate common_pre/2 does is recursively pattern-match to select the first code (C) from the head of the first list (string, [C|Cs]) in the list of all lists (all strings, [[C|Cs]|Ss]), and appends the matching code C to the result iff it is common to all (remaining) heads of all lists (strings), else it terminates.

Nice, clean, simple and efficient... :)

share|improve this answer
add comment

Combining answers by kennebec, Florian F and jberryman yields the following Haskell one-liner:

commonPrefix l = map fst . takeWhile (uncurry (==)) $ zip (minimum l) (maximum l)

With Control.Arrow one can get a point-free form:

commonPrefix = map fst . takeWhile (uncurry (==)) . uncurry zip . (minimum &&& maximum)
share|improve this answer
add comment
Python 2.6 (r26:66714, Oct  4 2008, 02:48:43) 

>>> a = ['interspecies', 'interstelar', 'interstate']

>>> print a[0][:max(
        [i for i in range(min(map(len, a))) 
            if len(set(map(lambda e: e[i], a))) == 1]
        ) + 1]

  • i for i in range(min(map(len, a))), number of maximum lookups can't be greater than the length of the shortest string; in this example this would evaluate to [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

  • len(set(map(lambda e: e[i], a))), 1) create an array of the i-thcharacter for each string in the list; 2) make a set out of it; 3) determine the size of the set

  • [i for i in range(min(map(len, a))) if len(set(map(lambda e: e[i], a))) == 1], include just the characters, for which the size of the set is 1 (all characters at that position were the same ..); here it would evaluate to [0, 1, 2, 3, 4, 5]

  • finally take the max, add one, and get the substring ...

Note: the above does not work for a = ['intersyate', 'intersxate', 'interstate', 'intersrate'], but this would:

 >>> index = len(
         filter(lambda l: l[0] == l[1], 
             [ x for x in enumerate(
 >>> a[0][:index]
share|improve this answer
Neat. Checking the sizes of vertical sets is smart –  mislav Dec 16 '09 at 17:55
add comment

Doesn't seem that complicated if you're not too concerned about ultimate performance:

def common_substring(data)
  data.inject { |m, s| s[0,(0..m.length).find { |i| m[i] != s[i] }.to_i] }

One of the useful features of inject is the ability to pre-seed with the first element of the array being interated over. This avoids the nil memo check.

puts common_substring(%w[ interspecies interstelar interstate ]).inspect
# => "inters"
puts common_substring(%w[ feet feel feeble ]).inspect
# => "fee"
puts common_substring(%w[ fine firkin fail ]).inspect
# => "f"
puts common_substring(%w[ alpha bravo charlie ]).inspect
# => ""
puts common_substring(%w[ fork ]).inspect
# => "fork"
puts common_substring(%w[ fork forks ]).inspect
# => "fork"

Update: If golf is the game here, then 67 characters:

def f(d)d.inject{|m,s|s[0,(0..m.size).find{|i|m[i]!=s[i]}.to_i]}end
share|improve this answer
No, this isn't golf. I actually had to look the phrase up to know what it means :) By "elegant code" I meant code that is readable, understandable and clever. Removing whitespace and shortening method/variable names is opposite from readable and understandable, and does not make the solution any more clever. Thanks for the inject tip! Wasn't aware of that. –  mislav Dec 16 '09 at 23:38
I know what you're saying about golfing, but couldn't let Jordan's effort go unchallenged. –  tadman Dec 17 '09 at 17:40
add comment

This one is very similar to Roberto Bonvallet's solution, except in ruby.

chars = %w[interspecies interstelar interstate].map {|w| w.split('') }
chars[0].zip(*chars[1..-1]).map { |c| c.uniq }.take_while { |c| c.size == 1 }.join

The first line replaces each word with an array of chars. Next, I use zip to create this data structure:

[["i", "i", "i"], ["n", "n", "n"], ["t", "t", "t"], ...

map and uniq reduce this to [["i"],["n"],["t"], ...

take_while pulls the chars off the array until it finds one where the size isn't one (meaning not all chars were the same). Finally, I join them back together.

share|improve this answer
Didn't know ruby had a take_while—thanks! –  mislav Dec 17 '09 at 9:43
add comment

A javascript version based on @Svante's algorithm:

function commonSubstring(words){
    var iChar, iWord,
        refWord = words[0],
        lRefWord = refWord.length,
        lWords = words.length;
    for (iChar = 0; iChar < lRefWord; iChar += 1) {
        for (iWord = 1; iWord < lWords; iWord += 1) {
            if (refWord[iChar] !== words[iWord][iChar]) {
                return refWord.substring(0, iChar);
    return refWord;
share|improve this answer
Simple way, i <3 your solution –  bumpmann Jun 4 '13 at 8:53
add comment

Here's a solution using regular expressions in Ruby:

def build_regex(string)
  arr = []
  arr << string.dup while string.chop!

def substring(first, *strings)
  strings.inject(first) do |accum, string|
share|improve this answer
I'm interested in how it performs. I can't make up my mind if it would be faster or slower than the reference solution(s). But I know you're already writing benchmarks ;) waits patiently –  mislav Dec 16 '09 at 17:56
You don't need regular expressions, because all you need is linear string comparison. This implementation is particularly inefficient because you build a new regex in each iteration. –  Svante Dec 16 '09 at 19:52
add comment

I would do the following:

  1. Take the first string of the array as the initial starting substring.
  2. Take the next string of the array and compare the characters until the end of one of the strings is reached or a mismatch is found. If a mismatch is found, reduce starting substring to the length where the mismatch was found.
  3. Repeat step 2 until all strings have been tested.

Here’s a JavaScript implementation:

var array = ["interspecies", "interstelar", "interstate"],
    prefix = array[0],
    len = prefix.length;
for (i=1; i<array.length; i++) {
    for (j=0, len=Math.min(len,array[j].length); j<len; j++) {
        if (prefix[j] != array[i][j]) {
            len = j;
            prefix = prefix.substr(0, len);
share|improve this answer
This is inefficient because you likely make comparisons that are superfluous when a later string further shortens the result. –  Svante Dec 16 '09 at 19:48
add comment

Instead of sorting, you could just get the min and max of the strings.

To me, elegance in a computer program is a balance of speed and simplicity. It should not do unnecessary computation, and it should be simple enough to make its correctness evident.

I could call the sorting solution "clever", but not "elegant".

share|improve this answer
add comment

The accepted solution is broken (for example, it returns a for strings like ['a', 'ba']). The fix is very simple, you literally have to change only 3 characters (from indexOf(tem1) == -1 to indexOf(tem1) != 0) and the function would work as expected.

Unfortunately, when I tried to edit the answer to fix the typo, SO told me that "edits must be at least 6 characters". I could change more then those 3 chars, by improving naming and readability but that feels like a little bit too much.

So, below is a fixed and improved (at least from my point of view) version of the kennebec's solution:

function commonPrefix(words) {
  max_word = words.reduce(function(a, b) { return a > b ? a : b });
  prefix   = words.reduce(function(a, b) { return a > b ? b : a }); // min word

  while(max_word.indexOf(prefix) != 0) {
    prefix = prefix.slice(0, -1);

  return prefix;

(on jsFiddle)


share|improve this answer
add comment

Golfed JS solution just for fun:

w=["hello", "hell", "helen"];
    return r;
share|improve this answer
add comment

Fun alternative Ruby solution:

def common_prefix(*strings)
  chars  = strings.map(&:chars)
  length = chars.first.zip( *chars[1..-1] ).index{ |a| a.uniq.length>1 }

p common_prefix( 'foon', 'foost', 'forlorn' ) #=> "fo"
p common_prefix( 'foost', 'foobar', 'foon'  ) #=> "foo"
p common_prefix( 'a','b'  )                   #=> ""

It might help speed if you used chars = strings.sort_by(&:length).map(&:chars), since the shorter the first string, the shorter the arrays created by zip. However, if you cared about speed, you probably shouldn't use this solution anyhow. :)

share|improve this answer
add comment

Javascript clone of AShelly's excellent answer.

Requires Array#reduce which is supported only in firefox.

var strings = ["interspecies", "intermediate", "interrogation"]
var sub = strings.reduce(function(l,r) { 
    while(l!=r.slice(0,l.length)) {  
        l = l.slice(0, -1);
    return l;
share|improve this answer
This traverses each string once for every character not in the result; e.g., a string that is the result plus 10 characters gets traversed 10 times. This is not very efficient. –  Svante Dec 16 '09 at 20:13
add comment

This is by no means elegant, but if you want concise:

Ruby, 71 chars

def f(a)b=a[0];b[0,(0..b.size).find{|n|a.any?{|i|i[0,n]!=b[0,n]}}-1]end

If you want that unrolled it looks like this:

def f(words)
  first_word = words[0];
  first_word[0, (0..(first_word.size)).find { |num_chars|
    words.any? { |word| word[0, num_chars] != first_word[0, num_chars] }
  } - 1]
share|improve this answer
Apparently this doesn't work on single-element arrays, but otherwise is pretty compact. –  tadman Dec 16 '09 at 18:43
Add the line return first_word if words.length==1 as the second line of the function and it should handle single-element arrays as well. –  bta Dec 16 '09 at 18:48
add comment

It's not code golf, but you asked for somewhat elegant, and I tend to think recursion is fun. Java.

/** Recursively find the common prefix. */
public String findCommonPrefix(String[] strings) {

    int minLength = findMinLength(strings);

    if (isFirstCharacterSame(strings)) {
    	return strings[0].charAt(0) + findCommonPrefix(removeFirstCharacter(strings));
    } else {
    	return "";

/** Get the minimum length of a string in strings[]. */
private int findMinLength(final String[] strings) {
    int length = strings[0].size();
    for (String string : strings) {
    	if (string.size() < length) {
    		length = string.size();
    return length;

/** Compare the first character of all strings. */
private boolean isFirstCharacterSame(String[] strings) {
    char c = string[0].charAt(0);
    for (String string : strings) {
    	if (c != string.charAt(0)) return false;

    return true;

/** Remove the first character of each string in the array, 
    and return a new array with the results. */
private String[] removeFirstCharacter(String[] source) {
    String[] result = new String[source.length];
    	result[i] = source[i].substring(1);	
    return result;
share|improve this answer
I will not condemn recursion, but you are building a new string for concatenating each character of the result. Otherwise, the approach is ok. –  Svante Dec 16 '09 at 20:47
add comment

A ruby version based on @Svante's algorithm. Runs ~3x as fast as my first one.

 def common_prefix set 
     rest.each{|e|return set[0][0...i] if e[i]!=c}
share|improve this answer
add comment

Oftentimes it's more elegant to use a mature open source library instead of rolling your own. Then, if it doesn't completely suit your needs, you can extend it or modify it to improve it, and let the community decide if that belongs in the library.

diff-lcs is a good Ruby gem for least common substring.

share|improve this answer
add comment

My solution in Java:

public static String compute(Collection<String> strings) {
    if(strings.isEmpty()) return "";
    Set<Character> v = new HashSet<Character>();
    int i = 0;
    try {
        while(true) {
            for(String s : strings) v.add(s.charAt(i));
            if(v.size() > 1) break;
    } catch(StringIndexOutOfBoundsException ex) {}
    return strings.iterator().next().substring(0, i);
share|improve this answer
add comment

Here's an efficient solution in ruby. I based the idea of the strategy for a hi/lo guessing game where you iteratively zero in on the longest prefix.

Someone correct me if I'm wrong, but I think the complexity is O(n log n), where n is the length of the shortest string and the number of strings is considered a constant.

def common(strings)
  lo = 0
  hi = strings.map(&:length).min - 1
  return '' if hi < lo

  guess, last_guess = lo, hi

  while guess != last_guess
    last_guess = guess
    guess = lo + ((hi - lo) / 2.0).ceil

    if strings.map { |s| s[0..guess] }.uniq.length == 1
      lo = guess
      hi = guess

  strings.map { |s| s[0...guess] }.uniq.length == 1 ? strings.first[0...guess] : ''

And some checks that it works:

>> common %w{ interspecies interstelar interstate }
=> "inters"

>> common %w{ dog dalmation }
=> "d"

>> common %w{ asdf qwerty }
=> ""

>> common ['', 'asdf']
=> ""
share|improve this answer
add comment

Your Answer


