if string is a subsequence of another

bool (sub, s):
    if s == null || sub == null:
        throw
    if sub.length() > s.length():
        return false
    for i = 0, j = 0; i < s.length() && j < sub.length(); i++:
        if s[i] == sub[j]:
            j++
    return j == sub.length()

Follow-up: There are multiple strings to check.

Keep a ch->indexes map for s. For each ch of sub, get the first index as i which is greater than previ (i of previous ch).

(subs, s):
    subCount = 0
    cindexMap = createIndexMap(s)
    for sub in subs:
        if isSubsequence(sub, cindexMap);   
            subCount++
    
bool isSubsequence(sub, cindexMap):
    previ = -1
    for c in sub:
        if !cindexMap.hasKey(c):
            return false
        indexs = cindexMap[c]
        i = -1
        // could use binary search
        for index in indexs:
            if index > previ:
                i = index
                break
        if i == -1:
            return false
        previ = i
    return true
    
map createIndexMap(s):
    // c->indexs map, indexs is list
    cindexMap = new
    for i = 0, i < t.length(), i++:
        c = t[i]
        if !cindexMap.hasKey(c):
            indexs = new list()
            cindexMap[c] = indexs
        else:
            indexs = cindexMap[c]
        indexs.add(i)
    return cindexMap

It's easier to check by generating all sub-sequences using combinations (uses O(2^n) space).

(subs, s):
    subCount = 0
    combinations = combine(s)
    for sub in combinations:
        subSet.add(sub)
    for sub in subs:
        if subSet.has(sub):
            subCount++

// for abc, gives
// a
// ab
// abc
// ac
// b
// bc
// c
[] combine(s):

[Hat tip to LeCo]