While working with strings, many times, we can come across a use case in which we need to find if a string has in it the repeating substring, which repeats all over the string and thus makes a multiple of the root substring. Let’s discuss certain ways in which we can get the root substring of a string.
Method #1: Using List comprehension + Brute Force We can perform this task using selective slicing and brute force manner. This is the naive method to find the string in which we try to get the root string by repetitive division of string.
Python3
# Python3 code to demonstrate working of # Check if string repeats itself # Using List comprehension + Brute Force # initializing string test_str = "LazyroarLazyroarLazyroar"# printing original string print("The original string is : " + test_str) # using List comprehension + Brute Force # Check if string repeats itself res = Nonefor i in range(1, len(test_str)//2 + 1): if (not len(test_str) % len(test_str[0:i]) and test_str[0:i] * (len(test_str)//len(test_str[0:i])) == test_str): res = test_str[0:i] # printing result print("The root substring of string : " + res) |
The original string is : LazyroarLazyroarLazyroar The root substring of string : Lazyroar
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #2: Using list slicing + find() This problem can also be solved using the fact that we can search for a root string after adding a string and checking the root string in this string except for the last and first character, which represents the string repeating itself. Doesn’t work for string length < 2.
Python3
# Python3 code to demonstrate working of # Check if string repeats itself # Using list slicing + find() # initializing string test_str = "LazyroarLazyroarLazyroar"# printing original string print("The original string is : " + test_str) # using list slicing + find() # Check if string repeats itself res = Nonetemp = (test_str + test_str).find(test_str, 1, -1) if temp != -1: res = test_str[:temp] # printing result print("The root substring of string : " + res) |
The original string is : LazyroarLazyroarLazyroar The root substring of string : Lazyroar
Time Complexity: O(n)
Auxiliary Space : O(n)
Method #3 Using re
This approach uses a regular expression to find the root substring of the string. The regular expression r’^(\w+?)\1*$’ matches any word character (\w) one or more times (+) until the end of the string
Python3
# Python3 code to demonstrate working of# Check if string repeats itself# Using the re moduleimport re# initializing stringtest_str = "LazyroarLazyroarLazyroar"# printing original stringprint("The original string is : " + test_str)# Using the re module# Check if string repeats itselfres = re.findall(r'^(\w+?)\1*$', test_str)[0]# printing resultprint("The root substring of string : " + res)#This code is contributed by Edula Vinay Kumar Reddy |
The original string is : LazyroarLazyroarLazyroar The root substring of string : Lazyroar
The time complexity of the regular expression approach using the re module is O(n), where n is the length of the string. This is because the findall method needs to iterate through the entire string to find all the matches for the regular expression.
The auxiliary space of this approach is also O(n), as the findall method will store all the matches in a list, which will have a length equal to the number of matches found. In this case, the list will have a length of 1, as the regular expression is designed to only find a single match. However, in general, the space complexity will depend on the complexity of the regular expression and the number of matches it finds.
Approach#4:using string manipulation
Algorithm
1.Initialize a variable called substring to an empty string.
2.Iterate over each character in the given string.
3.Add the character to the substring variable.
4.Check if the substring repeated multiple times forms the original string.
5.If a repeating substring is found, print the substring and return. Otherwise, continue iterating.
6.If the end of the string is reached and no repeating substring is found, print “No repeating substring found”
Python3
def check_repeating_substring(s): n = len(s) substring = "" for i in range(n): substring += s[i] if substring * (n//len(substring)) == s: print("The root substring of string :", substring) return print("No repeating substring found")# Example usagecheck_repeating_substring("LazyroarLazyroarLazyroar") # Output: The root substring of string : Lazyroar |
The root substring of string : Lazyroar
Time complexity: O(n^2), where n is the length of the input string. The outer loop iterates over each character in the string, and the string multiplication operation takes linear time in the length of the input string.
Space complexity: O(n), as we are using a variable called substring to store the substring as we iterate over the input string.
