Given a String and a character K, find longest substring length of K.
Input : test_str = ‘abcaaaacbbaa’, K = b
Output : 2
Explanation : b occurs twice, 2 > 1.Input : test_str = ‘abcaacccbbaa’, K = c
Output : 3
Explanation : Maximum times c occurs is 3.
Method #1: Using loop
This is brute way to solve this problem, in this, when K is encountered, counter is maintained till other character occurs, and count is noted, the maximum of these counts is kept and is returned as result.
Python3
# Python3 code to demonstrate working of # Longest Substring of K# Using loop# initializing stringtest_str = 'abcaaaacbbaa'# printing original Stringprint("The original string is : " + str(test_str))# initializing K K = 'a'cnt = 0res = 0for idx in range(len(test_str)): # increment counter on checking if test_str[idx] == K: cnt += 1 else: cnt = 0 # retaining max res = max(res, cnt)# printing result print("The Longest Substring Length : " + str(res)) |
The original string is : abcaaaacbbaa The Longest Substring Length : 4
Method #2: Using findall() + max()
In this, we get all the possible substrings of K using findall() and max() is used over it to get maximum length with len as key.
Python3
# Python3 code to demonstrate working of # Longest Substring of K# Using findall() + max()import re# initializing stringtest_str = 'abcaaaacbbaa'# printing original Stringprint("The original string is : " + str(test_str))# initializing K K = 'a'# getting all substringsres = re.findall(r'' + K + '+', test_str)# getting maximum of substrings Lengthres = len(max(res, key = len))# printing result print("The Longest Substring Length : " + str(res)) |
The original string is : abcaaaacbbaa The Longest Substring Length : 4
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #3: Using itertools.groupby
Step-by-step Algorithm:
- Use itertools.groupby() to group characters in test_str by their values
- Filter out the groups where the character is not equal to K
- Generate a list of lengths of all remaining groups using list comprehension
- Return the maximum value in the list using max()
Python3
# Importing itertools moduleimport itertools# Initializing input string and the character to be searchedtest_str = 'abcaaaacbbaa'K = 'a'# printing the original stringprint("The original string is : " + str(test_str))# Using groupby() function to group the characters of the stringres = max([len(list(grp)) for char, grp in itertools.groupby(test_str) if char == K])# Printing the resultprint("The Longest Substring Length : " + str(res)) |
The original string is : abcaaaacbbaa The Longest Substring Length : 4
Time complexity: O(n) where n is the length of the input string test_str
Space complexity: O(1)
Method #4: Using generator expression, max() and re.split() function
- Importing the re module
- The test_str variable is initialized with the given string.
- re.split() is used to split the string by every character except K, using a regular expression.
- A generator expression is used to get the length of each substring generated by re.split().
- max() function is used to get the maximum length of the substrings.
- Printing the result.
Python3
import re# initializing stringtest_str = 'abcaaaacbbaa'# printing original Stringprint("The original string is : " + str(test_str))# initializing KK = 'a'# Using generator expression, max() and re.split() functionres = max(len(sub_str) for sub_str in re.split(f'[^{K}]', test_str))# printing resultprint("The Longest Substring Length : " + str(res)) |
The original string is : abcaaaacbbaa The Longest Substring Length : 4
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 5: Using Regular expression and max()
- Import the re module which provides support for regular expressions.
- Define the input string and the character to be searched for.
- Use re.findall() method to find all the occurrences of the character in the string.
- Use the max() function to find the longest substring of the character by comparing the lengths of all the substrings obtained from step 3.
- Print the length of the longest substring obtained in step 4.
Python3
# Python3 code to demonstrate working of # Longest Substring of K# Using Regular expression and max()# importing regular expression moduleimport re# initializing stringtest_str = 'abcaaaacbbaa'# printing original Stringprint("The original string is : " + str(test_str))# initializing K K = 'a'# find all occurrences of the charactermatches = re.findall(K + '+', test_str)# find the length of the longest substringres = len(max(matches, key=len))# printing result print("The Longest Substring Length : " + str(res)) |
The original string is : abcaaaacbbaa The Longest Substring Length : 4
Time complexity: O(n) where n is the length of the input string, as we need to traverse the string only once.
Auxiliary space: O(n) for storing the matches found using re.findall().
Method 6: Using numpy:
Step-by-step approach:
- Create a numpy array from the input string.
- Use the np.where() function to find the indices where the character K appears in the array.
- Use the np.diff() function to calculate the consecutive differences between the indices found in step 2.
- Use the np.max() function to find the maximum consecutive difference, which gives the length of the longest
- substring of the character K.
- Return the result.
Python3
import numpy as np# Initializing input string and the character to be searchedtest_str = 'abcaaaacbbaa'K = 'a'# creating a numpy array from the input stringarr = np.array(list(test_str))# finding the indices where the character K appearsindices = np.where(arr == K)[0]# finding the consecutive differences between indicesdifferences = np.diff(indices)# finding the maximum consecutive differenceres = np.max(differences)# printing the original string and the resultprint("The original string is : " + str(test_str))print("The Longest Substring Length : " + str(res))#This code is contributed by Rayudu. |
Output: The original string is : abcaaaacbbaa The Longest Substring Length : 4
Time Complexity:
Creating a numpy array from the input string takes O(n) time, where n is the length of the input string.
The np.where() function takes O(n) time to find the indices where the character K appears in the array.
The np.diff() function takes O(m) time, where m is the number of indices where the character K appears in the array.
The np.max() function takes O(m) time to find the maximum consecutive difference.
Therefore, the overall time complexity of the algorithm is O(n + m).
Auxiliary Space:
Creating a numpy array from the input string takes O(n) space, where n is the length of the input string.
The np.where() function returns an array of size m, where m is the number of indices where the character K appears in the array.
The np.diff() function creates a new array of size m-1.
Therefore, the overall space complexity of the algorithm is O(n + m).
Method #7: Using dynamic programming
Step-by-step approach:
- Initialize a 1D array dp of length n, where dp[i] represents the length of the longest substring of the input string that ends at index i.
- Initialize dp[0] to 1 if the first character of the input string is ‘a’, otherwise set it to 0.
- Iterate over the characters in the input string starting from index 1. If the current character is equal to the target character ‘a’, set dp[i] to dp[i-1] + 1. Otherwise, set dp[i] to 0.
- Keep track of the maximum value in the dp array.
- Return the maximum value in the dp array as the length of the longest substring.
Python3
# initializing stringtest_str = 'abcaaaacbbaa'# printing original Stringprint("The original string is : " + str(test_str))# initializing KK = 'a'# Using dynamic programmingn = len(test_str)dp = [0] * ndp[0] = 1 if test_str[0] == K else 0for i in range(1, n): if test_str[i] == K: dp[i] = dp[i-1] + 1 else: dp[i] = 0max_count = max(dp)# printing resultprint("The Longest Substring Length : " + str(max_count)) |
The original string is : abcaaaacbbaa The Longest Substring Length : 4
Time complexity: O(n), where n is the length of the input string.
Auxiliary space: O(n), as we are using a 1D array dp of length n to store the lengths of the longest substrings ending at each index of the input string.
