Paytm Interview Question(Find largest word in dictionary by deleting some characters of given string)

Question:

Find largest word in dictionary by deleting some characters of given string

Explanation:

Need to find the longest string in dictionary which can be formed by deleting some characters of the given ‘str’.

For Example:

List ["note", "carrot", "monkey", "just"]

 Result:

            just

Program:

def subSeq(str1, str2):
    m = len(str1)
    n = len(str2)
    j = 0
    i = 0
    while i < n and j < m:
        if str1[j] == str2[i]:
            j += 1
        i += 1
    return j == m

def longString(dict1, str1):
    result = ""
    length = 0
    for word in dict1:
        if length < len(word) and subSeq(word, str1):
            result = word
            length = len(word)
    return result

dict1 = ["note", "carrot", "monkey", "just"]
str1 = "notjust"
print(longString(dict1, str1))

                                                                ---------End---------