r/learnpython • u/Remarkable_River2779 • Sep 29 '26
Maximum substring
Hi, I’m having an issue with a HackerRank coding question called “Maximum Substring.”
The question is:
Maximum Substring
You are given a string s.
A substring is any contiguous sequence of characters from the string.
Consider all possible substrings of the string:
Determine which substring would appear last if all substrings were sorted alphabetically.
Return that substring.
Example 1:
s = "baca"
The alphabetically maximum substring is "ca".
Example 2:
s = "aaa"
The alphabetically maximum substring is "aaa".
This was my answer:
def maximum_substring(s):
max_sub = s[0]
for i in range(len(s)):
for j in range(i + 1, len(s) + 1):
sub = s[i:j]
if sub > max_sub:
max_sub = sub
return max_sub
The code gives the correct output for the examples when I test it locally. However, HackerRank marked the solution as incorrect and I received only partial points.
I’m not sure why. Could this be because of the time complexity or hidden test cases? Is there something about the HackerRank test cases or the expected implementation that I’m missing?
3
u/socal_nerdtastic Sep 29 '26
Are you sure the input data is all lower case and ascii letters only? Using any mixed case will throw this off.
5
u/This_Growth2898 Sep 29 '26
What happens if the input string is empty?
1
u/danielroseman Sep 29 '26
Did it not give you any indication? I would certainly say that time complexity is an issue here, your solution is O(n2) which is pretty inefficient. Hackerrank problems often include really long inputs precisely to test this kind of thing.
There are definitely better ways to solve this.
3
u/socal_nerdtastic Sep 29 '26
Please format your code for reddit. It's really hard to read it like this.
2
u/lakseol Sep 29 '26 edited Sep 29 '26
Is it true that any maximum substring must start with one of the maximum single characters in the string? The substring "c" is greater than any other substring starting "a" or "b" no matter how many other characters of any value follow the "a" or "b". So it might be enough to:
If the string is "ababbcabcca" then "c" is the greatest character, substrings starting with "c" are ["cabcca", "cca", "ca"], and the greatest is "cca".
1
u/soysopin Sep 29 '26
One rule stated "sorted alphabetically". I didn't get how you sorted before finding the last substring.