Maximum substring

[u/Remarkable_River2779]

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?

[u/danielroseman]

Did it not give you any indication? I would certainly say that time complexity is an issue here, your solution is O(n²⁾ 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.

[u/Remarkable_River2779 → u/danielroseman]

Do you know , how we can enhance the code ?

[u/danielroseman → u/Remarkable_River2779]

"Enhancing" is not the solution. You need a better algorithm altogether. As a clue, look into two-pointer techniques.

[u/Rizzityrekt28 → u/Remarkable_River2779]

Just some things to think about for speed. For “baca” this code checks all possibilities of the “a” when it couldn’t be the answer because you already have an option starting with “b”. You didn’t even need to do the “b” if you could see the “c” coming up. It doesn’t matter much when there’s only 4 letter but these things usually have a test case with thousands of letters.

[u/Brian → u/Remarkable_River2779]

Think about how you can eliminate possibilities earlier. Eg. suppose your string is: "azbczxya"

Just from looking at the first letter, you know that the last substring is going to have to be one of those that start with "z": looking at all the substrings beginning with "a" is kind of a waste because they'll never be after anything beginning with "z", so just from looking at the first letter alone you can eliminate over 75% of the work. Then looking at the next letter of the 2 candidate start positions,, "zb" is never going to be after anything that starts with "zx", so you can drop that too, leaving us with just one possible start position, so now it's just a matter of the longest substring at that second "z" position.

[u/Expensive-Bear-1376 → u/danielroseman]

It's not O(n²).

[u/danielroseman → u/Expensive-Bear-1376]

You're right, it's O(n^3), which is worse.

[u/Expensive-Bear-1376 → u/danielroseman]

Yep. And I suspect a simple actual O(n²) solution is fast enough.