7 ms·

Sure, but now do 11 at a time with a similar algorithm (which was part 2 of the problem).

mjburgess 4y ago
I've just submitted in order to see the second part, which just says "now look for 14 unique". I dont see the problem here, if you want a notation to express it, a macro for something like, 0 != 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 1 != 0, 2, 3, 4, 5, 6, 7, ... is straightforward, and could be parameterised on the window size.
- jstanley 4y ago
  That's fine, but it's O(n) in the window size whereas the xor trick is O(1).
  - mjburgess 4y ago
    The window size is always constant in the problem, so it's O(1) There shouldnt be a loop over the window size in solutions to this (particular) problem
    - deathanatos 4y ago
      TFA's implementation is using a loop over the window size to compare each character to all the other characters, to see if they're unique. So, the article's O(N * W²) is correct, but I agree, the window size is fixed and small; it's fair to boil it down to just O(N). (I never even considered doing a for loop like that to determine if the window is unique; I just histogram the window, and then check if all the values in the histogram are 1. If yes, unique. If I had been cleverer, I wouldn't rebuild the histogram as the window shifts, but there was no need for that. This is essentially the next solution TFA presents.)
  - deathanatos 4y ago
    Part 1 and part 2 are the same, only the window size varies. But within a part, the window size is constant. For most, it should have just meant that, if you hard-coded the window size during part 1, that you need to make it a parameter. But for both parts, the naïve solution should be O(N * W), where N is the input length, and W is the window size. Like a sibling says, since within a part the window size is fixed, it is acceptable to call it O(N). Edit: ah, I see what his solution is doing. It is correct. I need to adjust my definition of naïve, I guess. His is O(N * W²). You can still reasonably consider W² constant, though, I think. And he gets to what I would call the "naïve" solution. (Previously.) ~The "naïve solution" in the OP does not appear to be correct. Or at least, if it does work,~ it appears to do far more computation that it needs to. The "xor trick" is O(N), too. (There cannot be a more efficient solution, as the entire input must be considered in the worst case. TFA is correct that its final form omits W, though.)

I've just submitted in order to see the second part, which just says "now look for 14 unique". I dont see the problem here, if you want a notation to express it, a macro for something like, 0 != 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 1 != 0, 2, 3, 4, 5, 6, 7, ... is straightforward, and could be parameterised on the window size.

jstanley 4y ago
That's fine, but it's O(n) in the window size whereas the xor trick is O(1).
- mjburgess 4y ago
  The window size is always constant in the problem, so it's O(1) There shouldnt be a loop over the window size in solutions to this (particular) problem
  - deathanatos 4y ago
    TFA's implementation is using a loop over the window size to compare each character to all the other characters, to see if they're unique. So, the article's O(N * W²) is correct, but I agree, the window size is fixed and small; it's fair to boil it down to just O(N). (I never even considered doing a for loop like that to determine if the window is unique; I just histogram the window, and then check if all the values in the histogram are 1. If yes, unique. If I had been cleverer, I wouldn't rebuild the histogram as the window shifts, but there was no need for that. This is essentially the next solution TFA presents.)
- deathanatos 4y ago
  Part 1 and part 2 are the same, only the window size varies. But within a part, the window size is constant. For most, it should have just meant that, if you hard-coded the window size during part 1, that you need to make it a parameter. But for both parts, the naïve solution should be O(N * W), where N is the input length, and W is the window size. Like a sibling says, since within a part the window size is fixed, it is acceptable to call it O(N). Edit: ah, I see what his solution is doing. It is correct. I need to adjust my definition of naïve, I guess. His is O(N * W²). You can still reasonably consider W² constant, though, I think. And he gets to what I would call the "naïve" solution. (Previously.) ~The "naïve solution" in the OP does not appear to be correct. Or at least, if it does work,~ it appears to do far more computation that it needs to. The "xor trick" is O(N), too. (There cannot be a more efficient solution, as the entire input must be considered in the worst case. TFA is correct that its final form omits W, though.)