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:

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

Comment

Explore