Python – Longest Substring Length of K

Last Updated : 16 May, 2023

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 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)) 

Output

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 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)) 

Output

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 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)) 

Output

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 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))

Output

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 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)) 

Output

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 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.

Python3

# 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))

Output

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.