checking if a string is subsequence of another string

July 1, 2022

Two strings M and W are given, need to check if one is subsequence of another.

I tried the following:

def filterr(bigStr,smallStr,i):
res=''
for char in bigStr:
    if(char in smallStr[i:]):
        i+=1
        res+=char
return res

m,w=input().split()
if(m==w):
    print('YES')
else:
    if(len(m)<len(w)):
        m,w=w,m
    s=filterr(m,w,0)
    if(s==w): print('YES')
    else: print('NO')

I don’t understand what is wrong with my above code. It’s not working for some unknown testcases (on a coding site). I have tried all types of inputs that I can think of and it is giving the correct answer for all of them.
Examples:

i/p: "john johanna" o/p: YES

i/p: "ira ira" o/p: YES

i/p: "kayla jayla" o/p: NO

Please help in finding why my code is not working for some unknown testcases.

>Solution :

Think about a test case:

m = "baab"
w = "ab"

With your filterr implementation, filterr("baab", "ab", 0) will return "bb" not "ab". Since "bb" != "ab", it will not think "ab" as a subsequence of "baab". But it is clear that "ab" is a subsequence of "baab".

To solve this subsequence problem, I’d recommend using two pointers approach.

# assume len(s) <= len(t)
def is_subsequence(s, t):
    p1 = 0
    p2 = 0
    while p1 < len(s) and p2 < len(t):
        if s[p1] == t[p2]:
            p1 += 1
            p2 += 1
        else:
            p2 += 1
            
    return p1 == len(s)