New answers tagged time-limit-exceeded
3
Instead of treating each digit separately, you could compute the answer for each prefix. Similar to how Horner's method is fast for evaluating polynomials. Let's look at an example and how the answer changes when appending another digit:
567
=> 567 + 56 + 5 + 67 + 6 + 7
= 5*111 + 6*22 + 7*3
5678
=> 5*1111 + 6*222 + 7*33 + 8*4
(looks like 10 times ...
4
You are reducing the final result modulo 10⁹+7, but are storing intermediate results in full, slowing the summation.
Reduce ans as you go:
ans += int(n[i]) * (i+1) * ((10**(l-i)-1)//9)
ans %= 10000000007
You'll also need to find creative ways to reduce (10**(l-i)-1)//9 to more manageable size, for long input strings. Consider writing a function ...
1
The tests
You have test cases - that's already better than a majority of review requests here, so well done!
There seem to be some missing cases. For example, we have no tests where either argument is an empty string - it's a good idea to start with those so that we have to think about edge cases and perhaps error reporting to begin with.
We have very few ...
3
Improving performance
There are a few ways to improve performance. You already have the basic structure right:
Do a few quick checks to see if it's possible at all that there is a permutation in the string.
For every window position, do a quick check first to see if this could possibly be a permutation.
If it is indeed possible, do a full check.
In order ...
3
I try to avoid spelling out how apply a sliding window to the challenge at hand.
The whole point of a sliding window approach is to get independent of the size of the window and only spend effort on things entering and leaving it.
You do so with the character counts.
But method 1 even uses viewSize prominently.
Method 2 exchanges this for, say, alphabet size....
Top 50 recent answers are included