Problem 2

List all the sub-sequences of length n contained in a string s.

You obtain a sub-sequence by “erasing” the characters in s.

For example, here are all the sub-sequences with n = 2 of "apple":

"ap"
"al"
"ae"
"pp"
"pl"
"pe"
"le"

Functions:

is_subsequence(subtext, text)	Check if the subtext is a subsequence of text.
list_subsequences(text, length)	List all subsequences of size length in text.

is_subsequence(subtext: str, text: str) → bool

Check if the subtext is a subsequence of text.

>>> is_subsequence('pe', 'apple')
True

>>> is_subsequence('ep', 'apple')
False

Requires

• len(subtext) <= len(text)

list_subsequences(text: str, length: int) → Set[str]

List all subsequences of size length in text.

>>> sorted(list_subsequences("apple", 2))
['ae', 'al', 'ap', 'le', 'pe', 'pl', 'pp']

Requires

• 0 <= length <= len(text)

Ensures

• not (
      length > 0 and len(text) > 0 and len(set(text)) == len(text)
  )
  or len(result) == math.comb(len(text), length)
  

  (If all the characters are unique, the number of substrings equals the count of binary sequences len(text) long with length bits set)

• all(is_subsequence(item, text) for item in result)

• all(len(item) == length for item in result)