`set_includes` (string subsequence-containment) in Python 2

• AFNP. The loop condition j != hn is more idiomatically expressed as an exception:

  try:
      for c in needle:
          while haystack[j] < c:
              ....
  except IndexError:
      return False
  

• No naked loops. Factor the while haystack[j] < c: into a function. Among other benefits, it'd allow

      j = search_character(haystack[j:], c)
  

• The binary search for c seems more performant than linear. See bisect module.

I had an idea to just try to make the word by removing all the needed characters from the rack/haystack and see if it works. The idea also follows the "Easier to ask for forgiveness than permission" approach.

def set_includes(haystack, needle):
    haystack = list(haystack)
    try:
        for char in needle:
            haystack.remove(char)
        return True
    except ValueError:
        return False

Obviously, this will scale badly for cases where haystack == needle for larger string lengths (noticeable starting at about n >= 500), but it does not need sorting. So you will have to check whether or not this is more efficient for your use case.

Depending on how often the check would return false because needle does contain one or more letters that are not on the rack, sets can maybe help you to take a shortcut:

if set(haystack).issuperset(needle):
    # check if there are enough letters to build needle from haystack
    ...
else:
    # haystack does not contain all the letters needed to build needle
    return False

Just for fun: We here in Python have iterators, too :-D

def set_includes(haystack, needle):
    it1 = iter(haystack)
    it2 = iter(needle)
    char2 = next(it2)
    while True:
        try:
            char1 = next(it1)
        except StopIteration:
            return False
        if char2 < char1:
            return False

        if not char1 < char2:
            try:
                char2 = next(it2)
            except StopIteration:
                return True

If you move the last try: ... catch ...: a few levels outwards, you can get quite close to the structure of the possible implementation given on cppreference. Don't take this to serious though.

We can do a little bit better:

def set_includes(haystack, needle):
    it2 = iter(needle)
    char2 = next(it2)
    for char1 in haystack:
        if char2 < char1:
            return False

        if not char1 < char2:
            try:
                char2 = next(it2)
            except StopIteration:
                return True

    return False

Here, at least one of the try: ... catch ...:s is transformed into a proper loop.

Use str.index()

The lines:

    while j != hn and haystack[j] < c:
        j += 1

are basically trying to find the index of c in haystack. So just use str.index():

def set_includes(haystack, needle):
    try:
        i = -1
        for c in needle:
            i = haystack.index(c, i+1)

    except ValueError:
        return False

    return True

Or, if you prefer use str.find():

def set_includes(haystack, needle):
    i = -1
    for c in needle:
        i = haystack.find(c, i+1)
        if i<0:
            return False
    return True

itertools one-liner

Almost forgot, here's your one-liner:

from itertools import groupby

set_includes = lambda h, n:not any(h.find(''.join(g))<0 for _,g in groupby(n))