educative.io

Educative

Python Soln Using Previous Two Problems Algorithm

I was surprised to see that the solution posted for this did not mimic the algorithm from the previous two questions, and although I can see how their soln is better (keeping track of the indexes of the first occurred element rather than iterating until the count becomes 1 again), I think in light of getting muscle memory for these patterns my solution is more intuitive

So here it is:

Time Complexity is still O(N) since outer loop executes N times and the while loop processes each element once in the worst case. .:. O(N+N) = O(N)

Space Complexity is still O(K) where K is the number of distinct characters. If we are assuming the english alphabet is only used, this reduces to O(26) = O(1)

Essentially its the same alg from the previous two questions, but we alter the while loop condition to ensure that the substring we are working on all has distinct characters.

1 Like

Thank you for the solution, our approach is to equip the user with as many perspectives as we can when it comes to problem-solving, that’s why we chose a different way.