Python - Longest Substring Length of K

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 code to demonstrate working of  # Longest Substring of K # Using loop # initializing string test_str = 'abcaaaacbbaa' # printing original String print("The original string is : " + str(test_str)) # initializing K  K = 'a' cnt = 0 res = 0 for 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 code to demonstrate working of  # Longest Substring of K # Using findall() + max() import re # initializing string test_str = 'abcaaaacbbaa' # printing original String print("The original string is : " + str(test_str)) # initializing K  K = 'a' # getting all substrings res = re.findall(r'' + K + '+', test_str) # getting maximum of substrings Length res = 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:

1. Use itertools.groupby() to group characters in test_str by their values
2. Filter out the groups where the character is not equal to K
3. Generate a list of lengths of all remaining groups using list comprehension
4. Return the maximum value in the list using max()

# Importing itertools module import itertools # Initializing input string and the character to be searched test_str = 'abcaaaacbbaa' K = 'a' # printing the original string print("The original string is : " + str(test_str)) # Using groupby() function to group the characters of the string res = max([len(list(grp)) for char, grp in itertools.groupby(test_str) if char == K]) # Printing the 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 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.

import re # initializing string test_str = 'abcaaaacbbaa' # printing original String print("The original string is : " + str(test_str)) # initializing K K = 'a' # Using generator expression, max() and re.split() function res = max(len(sub_str) for sub_str in re.split(f'[^{K}]', test_str)) # 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 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 code to demonstrate working of  # Longest Substring of K # Using Regular expression and max() # importing regular expression module import re # initializing string test_str = 'abcaaaacbbaa' # printing original String print("The original string is : " + str(test_str)) # initializing K  K = 'a' # find all occurrences of the character matches = re.findall(K + '+', test_str) # find the length of the longest substring res = 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.

import numpy as np # Initializing input string and the character to be searched test_str = 'abcaaaacbbaa' K = 'a' # creating a numpy array from the input string arr = np.array(list(test_str)) # finding the indices where the character K appears indices = np.where(arr == K)[0] # finding the consecutive differences between indices differences = np.diff(indices) # finding the maximum consecutive difference res = np.max(differences) # printing the original string and the result print("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.

# initializing string test_str = 'abcaaaacbbaa' # printing original String print("The original string is : " + str(test_str)) # initializing K K = 'a' # Using dynamic programming n = len(test_str) dp = [0] * n dp[0] = 1 if test_str[0] == K else 0 for i in range(1, n): if test_str[i] == K: dp[i] = dp[i-1] + 1 else: dp[i] = 0 max_count = max(dp) # printing result print("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.