letters.rb

require 'rspec/autorun'

def letters(a, b)
  indexes = b.each_char.map do |letter|
    a.each_char.each_with_index.select {|l, _| l == letter }.map {|_, i| i }
  end

  start = indexes.shift

  if indexes.empty?
    [start]
  else
    start.product(*indexes).select {|x| x == x.sort }
  end
end

describe "letters" do
  let(:a) { "hello world" }

  specify "example 1" do
    letters(a, "e").should == [[1]]
  end

  specify "example 2" do
    letters(a, "l").should == [[2,3,9]]
  end

  specify "example 3" do
    letters(a, "el").should == [[1,2], [1,3], [1,9]]
  end

  specify "example 4" do
    letters(a, "lo").should == [[2,4], [2,7], [3,4], [3,7]]
  end

  specify "example 5" do
    letters(a, "lod").should ==  [ [2,4,10], [2,7,10], [3,4,10], [3,7,10] ]
  end
end

Here is my attempt, it was meant to be iterative. With some more effort the recursion could probably be unwound. This might be logically identical to one of the other solutions. https://gist.github.com/jlsync/7162908

def get_results(string, s_i, chars, c_i )
  finds = []
  while i = string.index(chars[c_i], s_i)
    if chars[c_i + 1]
      if more_finds = get_results(string, i + 1, chars , c_i + 1)
        finds += more_finds.map{|a| a.unshift(i)}
      else
        return nil
      end
    else
      finds << [i]
    end
    s_i = i + 1
  end
  return finds
end

def letters(a, b)
  return get_results(a, 0, b.split(//), 0 )
end

This one runs pretty fast (2+ times faster than the next fastest on haystacks > 100 chars and needles > 4 chars, and increasingly much better as the strings get larger).

def letters(haystack_str, needle_str)
  haystack = haystack_str.chars
  needle   = needle_str.chars

  @pos_cache   = haystack.each.with_index.with_object(Hash.new { |h, k| h[k] = [] }) { |(c, i), h| h[c] << i if needle.include?(c) }
  @match_cache = Hash.new { |h, k| h[k] = {} }
  matches(needle)
end

def matches(chars, current_pos = -1)
  return [[]] unless chars.any?

  char, *rest = *chars
  @match_cache[char][current_pos] ||= begin
    this_matches = @pos_cache[char].select { |candidate_pos| candidate_pos > current_pos }
    this_matches.each_with_object([]) do |this_pos, memo|
      matches(rest, this_pos).each do |rest_matches|
        memo << [this_pos, *rest_matches]
      end
    end
  end
end

Benchmarks here: https://gist.github.com/02fd396e56ca8a8d2efe

Wanted to try my luck, and it turned out very similar to other solutions. It was lots of fun, thanks! :-)

module Refines
  refine Array do
    def strictly_increasing?
      each_cons(2).all? {|x, y| x < y }
    end
  end

  refine String do
    def char_indexes
      each_char
        .with_index
        .with_object(Hash.new { |h, k| h[k] = [] }) { |(char, idx), hsh|
          hsh[char] << idx
        }
    end
  end
end

using Refines

def letter_match(target, str)
  first_set, *rest = target.char_indexes.values_at(*str.split(//))

  first_set.product(*rest).select { |arr| arr.strictly_increasing? }
end

Specs used:

describe "LetterMatch" do
  let(:a) { "hello world" }

  specify "single match" do
    expect(letter_match(a, "e")).to eq [[1]]
  end

  specify "single letter with multiple matches" do
    expect(letter_match(a, "l")).to eq [[2],[3],[9]]
  end

  specify "multiple matches, example 1" do
    expect(letter_match(a, "el")).to eq [[1,2], [1,3], [1,9]]
  end

  specify "multiple matches, example 2" do
    expect(letter_match(a, "lo")).to eq [[2,4], [2,7], [3,4], [3,7]]
  end

  specify "multiple matches, example 3" do
    expect(letter_match(a, "lod")).to eq [[2,4,10], [2,7,10], [3,4,10], [3,7,10]]
  end
end