Python | Substring Frequency between Uppercases

Sometimes while working with Strings, we can have a problem in which we have to find substrings that occur between the uppercases and find their frequencies. This is a very unique problem and has less of applications. Let us discuss certain ways in which this task can be performed.

Method #1 : Using groupby() + regex + loop 

The combination of the above functions can be used to perform this task. In this, we use groupby() to group the regex-extracted substrings. And all is compiled using loop. 

The original string is : GeEkSForGeEkS
The grouped Substring Frequency : {'Ge': 2, 'Ek': 2, 'S': 2, 'For': 1}

Method #2: Using dictionary comprehension + sorted() + groupby() + regex

The combination of the above functions can be used to perform this task. In this, the task of cumulation is performed using dictionary comprehension. 

The original string is : GeEkSForGeEkS
The grouped Substring Frequency : {'Ek': 2, 'For': 1, 'Ge': 2, 'S': 2}

Time Complexity: O(n)
Auxiliary Space: O(n)

Method #3 : Using isupper(),split(),list(),set(),remove(),count() methods

Approach:

1. Replace uppercase character with “*”+uppercase character(using isupper())
2. Split on * that will result in a list(using split())
3. Create a new list with unique strings of above list(using list(),set())
4. Create a dictionary with unique strings as key and its count in original list. (using count() method)

Example:

The original string is : GeEkSForGeEkS
The grouped Substring Frequency : {'S': 2, 'Ge': 2, 'Ek': 2, 'For': 1}

Time Complexity : O(N)
Auxiliary Space : O(N)

Method #4: Using regular expression and Counter()

• A regular expression pattern is defined to match all the substrings that start with an uppercase letter followed by zero or more lowercase letters.
• The re.findall() method is used to find all the matches of the pattern in the given string. This method returns a list of all the matches.
• The Counter() method is used to count the frequency of each match in the list.
• The resulting dictionary of the Counter() method is the desired output.

Example:

The original string is : GeEkSForGeEkS
The grouped Substring Frequency : {'Ge': 2, 'Ek': 2, 'S': 2, 'For': 1}

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.

Method #5: Using a for loop and string slicing

1. Initialize an empty dictionary res to store the substring frequencies.
2. Initialize a variable start to 0.
3. Loop through each character in the test_str starting from the second character.
4. If the current character is uppercase, slice the substring between start and the current index (exclusive) and add it to the res dictionary. Update the start variable to the current index.
5. After the loop, slice the substring between the last uppercase letter and the end of the string and add it to the res dictionary.
6. Print the res dictionary.

Example:

The original string is : GeEkSForGeEkS
The grouped Substring Frequency : {'Ge': 2, 'Ek': 2, 'S': 2, 'For': 1}

Time complexity: O(n), where n is the length of test_str.
Auxiliary space: O(k), where k is the number of unique substrings between uppercase letters in test_str.

Method #6: Using a list comprehension and zip

Steps:

1. Create a list comprehension that uses zip to iterate over the string and create substrings between uppercase letters.
2. Use a for loop to iterate over the list of substrings.
3. Use the count method to count the occurrences of the current substring in the original string.
4. Add the substring and its count to a dictionary.
5. Print the resulting dictionary.

Example:

The original string is : GeEkSForGeEkS
The grouped Substring Frequency : {'Ge': 2, 'Ek': 2, 'S': 2, 'For': 1}

Time complexity: O(n^2) (due to the use of the count method)
Auxiliary space: O(k) (where k is the number of distinct substrings)