Given two strings, check if substring characters occur in correct order in string.
Input : test_str = ‘neveropen’, K = ‘sees’ Output : True Explanation : “s” after that “ee” and then “s” is present in order in string 1.
Input : test_str = ‘neveropen’, K = ‘seef’ Output : False Explanation : Unordered String.
Method #1 : Using join() + generator expression + in operator
In this, we check we join all the characters which occur in the substring using join(), post that check if substring is present using in operator.
Python3
# Python3 code to demonstrate working of# Test substring order# Using join() + in operator + generator expression# initializing stringtest_str = 'neveropen'# printing original stringprint("The original string is : " + str(test_str))# initializing substringK = 'seek'# concatenating required charactersdef temp(sub): return ''.join(chr for chr in sub if chr in set(K))# checking in orderres = K in temp(test_str)# printing resultprint("Is substring in order : " + str(res)) |
The original string is : neveropen Is substring in order : True
Time Complexity: O(n)
Space Auxiliary: O(n)
Method #2 : Using all() + next() + generator expression
In this, we get the string with just substring characters using next() and generator expression, to check for order, all() operation is used for each character in substring.
Python3
# Python3 code to demonstrate working of # Test substring order# Using all() + next() + generator expression# initializing stringtest_str = 'neveropen'# printing original stringprint("The original string is : " + str(test_str))# initializing substringK = 'seek'# concatenating required characters using next()# all() used to test ordertest_str = iter(test_str)res = all(next((ele for ele in test_str if ele == chr), None) is not None for chr in K)# printing result print("Is substring in order : " + str(res)) |
The original string is : neveropen Is substring in order : True
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #3 : Using find() method
Python3
# Python3 code to demonstrate working of# Test substring order# initializing stringtest_str = 'neveropen'# printing original stringprint("The original string is : " + str(test_str))# initializing substringK = 'seek'ns = ""for i in test_str: if i in K: ns += ires = Falseif(ns.find(K) != -1): res = True# printing resultprint("Is substring in order : " + str(res)) |
The original string is : neveropen Is substring in order : True
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #4 : Using replace() and find() methods
Python3
# Python3 code to demonstrate working of# Test substring order# initializing stringtest_str = 'neveropen'# printing original stringprint("The original string is : " + str(test_str))# initializing substringK = 'seek'for i in test_str: if i not in K: test_str=test_str.replace(i,"")res=Falseif(test_str.find(K)!=-1): res=True# printing resultprint("Is substring in order : " + str(res)) |
The original string is : neveropen Is substring in order : True
Method #5 : Using operator.contains() method
Approach
- Replace all characters of test_str which are not present in K using replace() method
- Now check whether K is present in test_str using operator.contains() method
- Display the return value of operator.contains()
Python3
# Python3 code to demonstrate working of# Test substring order# initializing stringtest_str = 'neveropen'# printing original stringprint("The original string is : " + str(test_str))# initializing substringK = 'seek'for i in test_str: if i not in K: test_str=test_str.replace(i,"")import operatorres=operator.contains(test_str,K)# printing resultprint("Is substring in order : " + str(res)) |
The original string is : neveropen Is substring in order : True
Time Complexity : O(N) N- length of string
Auxiliary Space – O(1) because res is a single variable
Method 6 : using list comprehension and the all() function
Python3
# Python3 code to demonstrate working of# Test substring order# initializing stringtest_str = 'neveropen'# printing original stringprint("The original string is : " + str(test_str))# initializing substringK = 'seek'# using list comprehension and all()res = all(K[i] in test_str[test_str.find(K[i-1])+1:] for i in range(1, len(K)))# printing resultprint("Is substring in order : " + str(res)) |
The original string is : neveropen Is substring in order : True
The time complexity of this approach is O(n^2), where n is the length of the substring K, because for each character in K, we need to search through the remaining part of test_str to find its position.
The auxiliary space complexity is O(1), because we only use a few extra variables to store the current position in test_str, the previous position found by find(), and the result of the all() function. No additional data structures are created.
