`set_includes` (string subsequence-containment) in Python 2 I've implemented C++'s std::includes algorithm in Python, so that I can use it to efficiently implement a Scrabble "can I make this word" function:

def word_can_be_made_from_rack(word, rack):
    return set_includes(sorted(rack), sorted(word))


Here's the implementation, with some test cases:

def set_includes(haystack, needle):
    j = 0
    hn = len(haystack)
    for c in needle:
        while j != hn and haystack[j] &lt; c:
            j += 1
        if j == hn:
            return False
        if haystack[j] &gt; c:
            return False
        j += 1
    return True

assert set_includes('abcdef', 'af')
assert set_includes('abcdef', 'bce')
assert set_includes('abcdef', 'abcdef')
assert set_includes('aaaaa', 'a')
assert set_includes('aaaaa', 'aa')
assert set_includes('aaaaax', 'ax')
assert set_includes('abbbcxx', 'abc')


This is similar to Find if one list is a subsequence of another except that it assumes (and requires) that the two input strings are sorted.

The manual management of index j in this code doesn't feel very Pythonic. Am I missing an easier way to write this algorithm?

itertools one-liners will be accepted as answers, especially if they're more performant. :)
AFNP. The loop condition j != hn is more idiomatically expressed as an exception:

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

No naked loops. Factor the while haystack[j] &lt; 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.