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

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