Given a String, find the length of the longest consecution, in which K doesn’t appear.
Input : test_str = ‘neveropen is best for neveropen’, K = ‘e’
Output : 9
Explanation : from s in best to e in neveropen, 9th letter is “e”.Input : test_str = ‘neveropen’, K = ‘e’
Output : 7
Explanation : from k to e, 7th letter is e, longest run.
Method #1 : Using a loop
We perform this in 2 steps, in 1st we iterate for all elements to get indices of K, and then in the next step find the maximum difference between consecutive characters.
Python3
# Python3 code to demonstrate working of # Longest Consecution without K in String# Using loop# initializing stringtest_str = 'neveropen is best for neveropen'# printing original stringprint("The original string is : " + str(test_str))# initializing K K = 'e'# getting all indices indxs = []for idx, ele in enumerate(test_str): if ele == 'e': indxs.append(idx)# getting difference diffs = []for idx in range(len(indxs) - 1): diffs.append(indxs[idx + 1] - indxs[idx])# getting max diff using max()res = max(diffs)# printing result print("Longest run : " + str(res)) |
The original string is : neveropen is best for neveropen Longest run : 9
Method #2 : Using filter() + lambda + zip() + list comprehension + max()
In this, we get the index of K elements using filter() + lambda, and zip() + list comprehension is used to get differences between indices. Post that, max() is used for extracting the maximum difference.
Python3
# Python3 code to demonstrate working of # Longest Consecution without K in String# Using filter() + lambda + zip() + list comprehension + max()# initializing stringtest_str = 'neveropen is best for neveropen'# printing original stringprint("The original string is : " + str(test_str))# initializing K K = 'e'# getting all indices using filter + lambdaindxs = list(filter(lambda ele: test_str[ele] == 'e', range(len(test_str)))) # getting difference using zip()# negative index, for getting successive elements diffs = [j - i for i, j in zip(indxs[: -1], indxs[1 :])] # getting max diff res = max(diffs)# printing result print("Longest run : " + str(res)) |
The original string is : neveropen is best for neveropen Longest run : 9
The Time and Space Complexity for all the methods is the same:
Time Complexity: O(n)
Space Complexity: O(n)
Method #3: Using str.split() function
Algorithm:
- Initialize a string variable named test_str.
- Initialize a character variable named K.
- Split the test_str by the character K and store the substrings into a list variable named subs.
- Find the max length of substrings from the list of subs and add 1.
- Print the result.
Python3
# initializing stringtest_str = 'neveropen is best for neveropen'# printing original stringprint("The original string is : " + str(test_str))# initializing K K = 'e'# splitting string into substrings without Ksubs = test_str.split(K)# getting max length substring using max() and len()res = max(len(sub) for sub in subs) + 1# printing result print("Longest run : " + str(res)) |
The original string is : neveropen is best for neveropen Longest run : 9
Time complexity: O(n) where n is the length of the input string test_str.
Space complexity: O(n) where n is the length of the input string test_str.
Method #4: using itertools and reduce method:
Algorithm:
- Import the required modules itertools and functools.
- Initialize the string and the character.
- Split the string into groups of consecutive characters that are not K using group by function.
- Find the length of each group using the map function.
- Find the maximum length using reduce function.
- Print the original string and the longest run calculated.
Python3
# Python program for the above approachfrom itertools import groupbyfrom functools import reduce# Driver Codetest_str = 'neveropen is best for neveropen'K = 'e'# Split the string into groups of# consecutive characters that are not Kgroups = [list(g) for k, g in groupby(test_str, lambda x: x != K) if k]# Get the length of each group and# find the maximum lengthres = reduce(lambda acc, x: max(acc, len(x)), groups, 0)+1print("The original string is : " + str(test_str))print("Longest run : " + str(res))# This code is contributed by Jyothi Pinjala |
The original string is : neveropen is best for neveropen Longest run : 9
Time Complexity: O(N), The time complexity of the code is O(n) where n is the length of the input string. This is because we iterate through the input string only once.
Space Complexity: O(N), The space complexity of the code is O(n) where n is the length of the input string. This is because we create a list of groups that can have a length of at most n. The other variables created have constant space requirements.
has context menu
Method #4: Using map filter enumerate and lambda
- Initializing the list and k
- Using map(), a list of indices of the given character is obtained and stored in the ‘indxs’ variable.
- Using filter(), the values in the ‘indxs’ list that are greater than or equal to the length of the input string minus 1 are removed. The resulting list is then converted to a set and stored in the ‘indxs_set’ variable.
- Using max(), the maximum value in the ‘diffs
- Printing the result
Python3
# initializing stringtest_str = 'neveropen is best for neveropen'# printing original stringprint("The original string is : " + str(test_str))# initializing K K = 'e'# finding all the indices of K in the stringindxs = list(map(lambda x: x[0], filter(lambda x: x[1] == K, enumerate(test_str))))# finding the difference between the consecutive indicesdiffs = [indxs[i+1]-indxs[i] for i in range(len(indxs)-1)]# getting the longest consecution without Kres = max(diffs)# printing the resultprint("Longest run : " + str(res)) |
The original string is : neveropen is best for neveropen Longest run : 9
Time complexity: O(n), where n is the length of the input string.
Auxiliary Space: O(n), where n is the length of the input string.
