A neat XOR trick
mattkeeter.com
mattkeeter.com
But otherwise, yes.
I spent quite a while optimizing GCC's bitmap operations years ago, including implementing some new sparse bitmap types, and the sparse bitmap types i implemented ended up dependent on the speed of popcnt and friends, so yes.
Your algorithm will report a match at "bccd" since the "a" wasn't removed from the bitmask.
Unfortunately few other computers have included it before Cray 1, which made it well known, under the current name.
It is probably just a legend though.
The legend you're probably misremembering is the one where the NSA approached Seymor Cray at CDC while he was designing the 6600 super and 'suggested' that if he included a popcnt instruction in the ISA, the NSA would certainly look favorably on purchasing some. He did and they did (quite a few). This story is also possibly apocryphal.
Ok. Why??????????????
@gpderetta is correct at least in quoting hacker's delight where it was also said to be rumoured the NSA wanted popcount but it was unclear to HD's author why they wanted it.
Cryptography has advanced since then - and I'm not an expert - but there may still be statistical weaknesses that could be found by counting bits?
It accelerates the calculation of the Hamming weight of a vector or string. Hamming weight is useful lots of places in crypto, like helping frequency analysis, or observed power consumption attacks against crypto systems. It's useful in many other disciplines as well.
I would do it by storing the product of the counts; divide by the outgoing count before decrementing, multiply by the incoming count after incrementing. If the product is one they're all unique. Scaling should be comparable to POPCNT.
Doesn't B have a POPCNT?
B is mandatory in RVA22.
https://github.com/riscv/riscv-bitmanip/blob/main/bitmanip/i...
https://www.sifive.com/cores/performance-p650
Heres another:
https://www.andestech.com/en/2022/12/08/andes-technology-unv...
I expect all future Linux cores to have it
All RVA22 profile cores will, as RVA22 requires B extension.
>Sifive p650 will have it
Current versions of U74 also have it. And a U74 with B is already shipping in VisionFive 2.
That makes a bit weaker the case for using popcount, since that actually is O(W/Wordsize), which happens to be O(1) in this case.
If HashSet.insert ever returns false, the character was already in the set, and the window is not unique, so you can early exit and move on. If you get through the window without insert returning false, it is unique. You don't need to do anything else (like check the length of the hash set at the end)
You actually don't need any extra anything at all if you want, as you can just keep a single count because you don't need to look back at old windows, and can keep moving forward to the last non-unique point, making it O(N).
I'm sure this being HN, someone will come along and post how to do this.
I already got caught out once by trying to code it too fast so not gonna do it ;)
Something like this... this is psuedo code. You iterate through the string once. You pop an element off of the queue at most once. In this implementation you might add it to the queue twice.
def find_uniq_window(long_string, w):
queue = Queue()
hash_set = Hashset()
for char in long_string:
if queue.size() == w:
old_char = queue.pop()
hash_set.remove(old_char)
queue.push(char)
if char not in hash_set and queue.size() == w:
# success
return queue
if char in hash_set:
#empty the queue and hash set and start over
queue = Queue()
hash_set = HashSet()
queue.push(char)
hash_set.add(char)
# We never found the window of unique characters, so return false
return FalseAlso I think on `char in hash_set` you'd want to advance the start of the window until uniqueness is restored, rather than moving start to the end.
E.g. if the string is "abac", when you get to the second "a", instead of restarting the window at the second "a" you want to instead move the start to "b". You might even be able to do something boyer-moore-esque if the hashset is instead a hashmap of chars to index. Then you can directly advance your window by how far in the mismatch is, which probably won't affect asymptotic complexity since you still need to remove elements but allows you to do it in bulk rather than one at a time.
You could definitely use two indexes instead of a queue, and using indexes over an array will be faster than using a queue.
[0]: https://github.com/mpawelski/adventofcode2022_day06/blob/mas...
It's possible to store a doubly-linked list using only a single pointer per node. For entry B, &B = &A ^ &C. You can walk the list in either direction as long as you have pointers to two neighbouring nodes in the list. Half as much memory overhead compared to an implementation where each node stores two pointers.
Many leetcode-type problems are amenable to O(n) speedups using this technique.
For example, in a chess engine: if the hash value for "white knight on f3 square" is 0x8BADF00D and the hash value for "white king on e4 square" is 0x1BADB002, then a chess board containing only "white knight on f3 and white king on e4" would be hashed as (0x8BADF00D xor 0x1BADB002) = 0x9000400F.
The upside of this trick is that if your set can contain N different objects (e.g. 768 combinations of 12 different chess pieces on each of 64 squares), you don't need to use an N-bit hash value, which would be pretty big. In the particular problem described in this blog, this isn't an advantage as it's using a set containing only up to 26 letters, which neatly fits in a u32 even if you dedicate a bit to each letter.
However there are downsides to Zobrist hashing - it's very hard to guarantee that you don't get hash collisions in this manner, as AFAIK you'd have to try all combinations of valid sets, which is prohibitively expensive. So every algorithm relying on this hash value either has to be robust to hash collisions, or it accepts a small probability of failure.
Most importantly in this case, Zobrist hashing doesn't let you test whether a particular element is present in the set, nor does it let you count the number of elements in a set. So it wouldn't work as a solution to the problem in this blog, which requires counting how many unique letters are present in the hash value.
ChatGPT did offer a useful suggestion I'd never heard of when I asked it to describe The Mighty XOR:
>As I mentioned in my previous responses, XOR is a logical operation and does not have any physical form or abilities, so it cannot be a superhero. Therefore, it is not possible for a character named "The Mighty XOR" to be part of the Marvel universe or any other fictional universe, as they would not exist in reality. If you are interested in characters from the Marvel universe with powers related to digital logic or computing, you might consider the character of The Calculator from DC Comics, who has the ability to use his super-genius intellect to perform complex calculations and hack into computer systems. However, this character is not part of the Marvel universe and does not have the name "The Mighty XOR".
https://en.wikipedia.org/wiki/Calculator_(character)
>Calculator (Noah Kuttler) is a supervillain appearing in American comic books published by DC Comics. Originally introduced as one of many villains in Batman's rogues' gallery, the character was later redeveloped in the 2000s as a master information broker, hacker, and tactical supervisor to other supervillains, and foil to Batman's partner Oracle.
>[...] Calculator suffers from severe obsessive-compulsive disorder, unbeknownst to his peers (even though this was hinted at when he was in charge of monitoring Supergirl), and initially controlled this with medication.
I was quite impressed, here is the ChatGPT version:
fn run(s: &[char], window_size: usize) -> usize { let mut unique_chars = 0; for i in 0..window_size { unique_chars |= 1 << (s[i] as u32 - 'a' as u32); } if unique_chars.count_ones() as usize == window_size { return window_size; }
for i in 1..s.len() - window_size {
let prev = s[i - 1] as u32 - 'a' as u32;
let next = s[i + window_size - 1] as u32 - 'a' as u32;
unique_chars ^= 1 << prev;
unique_chars |= 1 << next;
if unique_chars.count_ones() as usize == window_size {
return i + window_size;
}
}
panic!("No unique window found");//NOTE: my prompt was the make the code O(N)
int main(void) {
char *c = 0, *data = "nznrnfrfntjfmvfwmzdfjlvtqnbhcprsg";
for (
c = data;
!((c[1] != c[0]) &&
((c[2] != c[1]) && (c[2] != c[0])) &&
((c[3] != c[2]) && (c[3] != c[1]) && (c[3] != c[0])));
c++
);
printf("%ld", c-data+4);
}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, ...
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.)
There shouldnt be a loop over the window size in solutions to this (particular) problem
(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.)
def main():
count = 1
for i in range(1, len(SIGNAL)):
for j in range(0, count):
if SIGNAL[i - j - 1] == SIGNAL[i]:
count = j
break
count = count + 1
if count == 4:
print(i + 1)
break
Edit: I think your solution already effectively does this, it's just that because you maintain invariant that the window always contains unique chars to avoid any additional datastructure, once the window start gets reset to "[g]" it needs to build back up the intermediate state one char a time to works it way back up to [gqwerty]. So the best case is approximately linear if count gets reset often, worst case is O(NW). The method I was thinking of directly tests the next window starting from its endpoint backwards, to do this you need a hashet. I think that would achieve on best case O(N/W) effectively sublinear, worst case is still O(NW) though.
This could happen if we are instead interested in a window of unique words in a long document.
Amazingly there is still a solution based on XOR!
It is a variant of Bloom Filters, which I know everyone loves, but it uses XOR instead of OR to combine things.
Basically each word is hashed to three locations and you flip those bits. Then you have to do some probabilistic analysis.
https://arxiv.org/abs/2211.03683
Edit: Actually the technique in this paper would take linear time to determine uniqueness. I wonder if there's a way to do it in constant time...
I guess you could just implement linear probing or cuckoo hashing in bits. But then update time would be amortized constant only.
You can xor arrays of integers.
If you have a huge string, a huge alphabet, and also a huge window, then probabilistic techniques start to make sense. But let's not run while we can successfully walk!
Edit - actually it should be possible to update the count incrementally, so it should still be O(N) I think.
Using a bitmap to track letters you've seen is a great idea. But the parity and counting gives me a headache. How about you start with a zero-size window at the start of the string, then iteratively try to grow it by moving the end forward until it's long enough, and if the character added would be a duplicate, moving the start forward until it's no longer a duplicate? Sort of inchworm-style movement.
I am not smart enough to write Rust, so here it is in Java:
private static int run(String input, int windowSize) {
int windowStart = 0; // start at the start
int windowEnd = 0; // the window is initially zero-size
int lettersSeen = 0; // a bitmap of letters we have seen
while (windowEnd - windowStart < windowSize) {
if (windowEnd >= input.length()) throw new IllegalArgumentException("No unique window found");
int letterToAdd = 1 << input.charAt(windowEnd) - 'a';
while ((lettersSeen & letterToAdd) != 0) {
// duplicate, slide the start until we drop the original
int letterToRemove = 1 << input.charAt(windowStart) - 'a';
assert (lettersSeen & letterToRemove) == letterToRemove; // sanity check that we have seen this letter
lettersSeen ^= letterToRemove;
++windowStart;
}
// add the new letter
assert (lettersSeen & letterToAdd) == 0; // sanity check that we have seen this letter
lettersSeen ^= letterToAdd;
++windowEnd;
}
return windowStart;
}
Note that although this has two nested loops, they don't both independently range over the whole string, so this is not O(n^2). The outer loop moves windowEnd over the whole string, and the inner one moves windowStart over the whole string bit by bit. Each index visits each position in the string at most once.
> i mask the bitmap in the inner loop condition, but you could just test letterToRemove against letterToAdd and break if they're the same
You still need to check ((lettersSeen & letterToAdd) != 0) once to know whether you need to enter that loop at all. Worst case (a long string of the same letter) you do this twice per letter in the input anyway.
I had to make zero changes, it appears to work.
https://graphics.stanford.edu/~seander/bithacks.html#CountBi...
mask = -1 << i;
return (x & ~mask) | ((x >> 1) & mask);
mask = -1 << i;
return ((x ^ (x >> 1)) & mask) ^ x;Does this technique catch letters duplicated more than once?
In a Python 3 shell:
>> 2 ^ 4
6
>> 2 ^ 4 ^ 2
4
>> 2 ^ 4 ^ 2 ^ 2
6
If you wanted to detect V unique characters from a window of W characters where V < W, this trick wouldn't work. But you could still have a rolling window, it would just be a map counting "how many of this character in the window", which you can increment the relevant character for as it enters the window, and decrement as it leaves.
Good catch; this should be fixed (using N for input length and W for window size consistently in the writeup).
There's actually whole classes of problems which would be more interesting if the naive solution wasn't fast enough, for example even on day 7 (or was it 8?) naively exploring to every edge from every square would be O(N^3) but still execute just fine.
I'm a couple of days behind but so far this year hasn't yet had lanternfish style problems where the naive solution blows up completely, but hopefully they will come as they are a lot more interesting.
projecteuler.net is great, but it _very_ quickly becomes deep math.
// Turn on bits as they enter the window
set ^= 1 << (s[i] as u32 - 'a' as u32);
// Turn off bits as they leave the window
if i >= window_size {
set ^= 1 << (s[i - window_size] as u32 - 'a' as u32);
}
It's a cool trick, but it didn't make the algorithm asymptotically more efficient as the OP suggests.
Reminds me of the problem “find the only missing number in a scrambled list of 1..n”. You can get an “O(n)” solution using xor, but once bit size becomes a concern, there are less hacky solutions that are just as fast.
The thing is that we usually saw you have random access to all of your input data in constant time. But if your input size is `n`, your pointer size must be `log n`. So for standard algorithm analysis to work, you need to allow a word size of at least `log n`.
We usually assume the pointer size to be infinite (e.g. RAM machine), to avoid having to deal with access time. But if we don't, then it must be a constant size (and we have to adjust the big O formulas accordingly). In neither of those cases do you get free arbitrary length xor operations. Just like you don't get e.g. free arbitrary length multiplications either.
One nice property of xor, however, is that you can parallelize the heck out of it. So you can get arbitrary constant factor improvements by adding a bunch of CPUs.
This is a nice model because you don't have to assume things like "infinite pointer sizes", and because the algorithms that work well in practice (such as using bit tricks) also work well in the theory.
If you don't work in the word ram model you also wouldn't be able to do things like hash maps with constant time queries, since that requires a hash function which can't be computed in O(1) bit operations.
Not to mention, a machine where addition takes O(1) time is a massive cheat - at least definitely not what most people have in mind when talking about computational complexity. AFAIK, O(...) usually means "on a classic RAM machine" unless otherwise stated. With hash maps/sets, it really depends on what is expected to grow. Bigger input size doesn't always mean bigger keys.
It's actually easy to do logn bit operations in O(1) time on the kind of machine you are talking about too. Just make a table with the result of all (lg n)/2 bit inputs. Such a table only takes sqrt(n) memory and time to create, and since you seem to accept O(1) table lookups you now have count_ones in two lookups.
Similarly it's easy to make small tables that allow you to do arbitrary binary operations on (lg n)/4 bit strings.
> at least definitely not what most people have in mind when talking about computational complexity.
I'm pretty sure if you look in CLRS or any standard text book of algorithms, they allow lgn bit operations in constant time. Every heard people saying "Sorting takes O(n logn) time"? They are clearly assuming comparing two numbers can be done in constant time.
Also look at any lecture notes from actual CS researchers, like this: http://www.cs.cmu.edu/~odonnell/toolkit13/Lecture05.pdf
> Doesn’t that imply that we need w ≥ log n?
> Answer: Yes! And that’s a standard assumption! The first time you see this it may seem totally weird: you’re assuming the computer hardware size depends on the input size?! That seems to make no sense. But once you calm down, it’s actually quite logical and cool. Of course you want a single pointer to fit into a word. You should just think of w as a parameter of the model, and w ≥ log n as an assumption.
Where n is the number of items. Not the number of digits! And we don't normally talk about "time" when discussing sorting algorithms in the first place. We talk about number of comparisons (precisely because we have no clue how big the items are!).
> Just make a table with the result of all (lg n)/2 bit inputs
We're interested in the number of ones in a C-bit integer, where C is the size of the character set (and incidentally the maximum acceptable value of the window size W). Simply counting the ones bit by bit costs O(C) time. Making a lookup table for all (C/2)-bit numbers - as you seem to suggest - costs O(2^(C/2)) time and space. And the algorithm we wanted to improve runs in O(N * C) time.
Look, I'm trying to decipher what your point is, but you seem to be confusing the size of the input space with the size of the input. So AFAIC, this is as much attention as this algorithm deserves. It's a nice party trick, but nothing more.
Sure you might be a purist and talk about comparisons, but I'm pretty sure if you Google it most people would talk about time. And "n logn" is exactly the amount of time it takes to sort n word-length integers in Word RAM.
> We're interested in the number of ones in a C-bit integer
You're not really engaging with the point that you can make a table in sqrt(n) time that allows counting the bits in logn bit strings in constant time. That means the final algorthm runs in O(NC/logN) time.
This is definitely not a party trick, as you would know if you've ever written a program using these methods. Now with AVX instructions it's more important than ever.
You also didn't engage with O'Donnells lecture notes. I can find you many more text books explaining why this is the right assumption to make, in case you don't like the reasons I've given above.
Edit: More generally, I feel like these sorts of tricks are getting less relevant over time. With the prevalence of Unicode text how many clever interview question optimizations that assume characters are just another way of saying u8 are no longer relevant?
The moral is knowledge is king and no matter how much iron you throw at a problem a well-designed algorithm will beat it.
Part of the meta-game to AoC is knowing that you can limit your answer to only the requirements in the combination of the question and input given. If the naive solution runs fast enough, and is vastly quicker to implement, that's the one you want.
Wikipedia gives an example. [0] Many courses on algorithms and/or complexity theory emphasise such examples in their introductions.
That said I don't know why jhoechtl thought that was the moral of this blog post, which doesn't illustrate that point at all.
[0] https://en.wikipedia.org/wiki/Computational_complexity#Use_i...
Standupmaths - "Someone improved my code by 40,832,277,770%": https://www.youtube.com/watch?v=c33AZBnRHks (OK, 41 billion percent is only 0.41 billion times better, but still.)
All I was trying to say is that beyond a point, it's not _just_ the algorithm, you need to pay attention to mechanical sympathy.
Do well-designed algorithms outperform naive algorithms? Almost always. Is designing the algorithm well sufficient? I'd think not.
https://github.com/frohoff/jdk8u-jdk/blob/master/src/share/c...
Where add() uses `|= bitmask`, remove() uses `&= ~bitmask`, and size() uses a count of the 1's in the long.
Adding XOR as an efficient toggle would be interesting, but unnecessary to keep this O(n), if I understand correctly. It's just toggling the value, so (albeit with an extra branch), you could implement it as:
if (!set.contains(val)) {
set.add(val);
} else {
set.remove(val);
}Then a friend solved it with regular expressions, but I found a sicker regex. After all, that's what regexes are about.
https://mobile.twitter.com/erikcorry/status/1600524753596456...
Edit: I misread the post; my bad. The post effectively uses a bit vector to store the last N chars in a window, and the bit vector happens to fit in a single machine word. Also, XOR happens to be a good way to update the bit vector, because it turns out it's sufficient to store how many times each character appears in the window mod 2.
So to be clear, my "demonstration" above only works because the ASCII representations of e, f, and g are not linearly independent with respect to xor. However in the article, the representations of all of the characters are chosen to be a linearly independent set.
The running time is does not depend on the window length, but does depend on the number of possible characters. If it's all of Unicode for example you'd be stuffed: you could fix the vector of values in memory (currently there are approx. 150,000 unicode code points), even if you used a byte per value, but counting number of true values will require iterating over the whole vector.
Even just going from 26 Latin letters to 256 byte values makes this trick quite messy unless your language has a really nice bit vector type (admittedly many do).
This comment was helpful for me to understand what was going on, even though it's a mistake followed by a correction.
1 << (s[i + j] as u32 - 'a' as u32)Then you've just got a standard single 1 left shifted 0-25 positions. (So 'a' is 1 and 'z' is 1*2^25.)
old bit mask = current bit mask
current bit mask = current bit mask OR new character
if old bit mask == current bit mask
window is not unique, move to the next window
(otherwise window is so far unique)This should work:
init bit mask and count of bits to 0
for each new char:
old = bit mask
bit mask = bit mask XOR old char
if bitmask > old then count++ else count--
old = bit mask
bit mask = bit mask XOR new char
if bitmask > old then count++ else count--
if count == window length: return match
But if there is a POPCNT instruction it would probably be faster to use it.
You can add an early return to the OPs XOR method by just checking if the char is already in the bit mask. This will be faster if the word size is large.
That said, I agree you can make the bit munging faster in the end, i'm just saying i don't think the speed up is anywhere near the improvement from early-exiting.
Bit operations and shifts take a single clock cycle, and the mask can be stored in a register throughout the entire loop.
If "early exit" brings any improvement, I don't see why the best wouldn't be to combine the two solutions instead of choosing one or the other.
This is known as a perfect hash[1]. knowing that you will never have collisions does allow for a faster implementation. The hash map can be backed by an array which will never need to be resized, and you don't have to fiddle with linked lists to chain collisions.
You're correct though, that this is something you will have to implement yourself. Library hashmaps are going to trade performance for general usefulness.
One would have to test ti see where the cutoff is, but often doing extra work is faster.
Edit: but this is discussed elsethread.
A fixed size run also helps with vectorization.
new_mask = old_mask XOR old_char XOR new_char
count += signum(new_mask - old_mask)
e.g.
old mask = 011100 new mask = 001111, numerically less even though it has one more bit set
It doesn’t change the fact that problem is incremental, and most importantly you can early exit windows as soon as you discover a single non-unique character. You don't have to wait till the end of the window. They don’t implement this for hash set, for example.
Since most (n>1) windows are not unique (well, more accurately the probability of the window being unique decreases as the size of the window approaches the number of possible characters), early exit from windows will likely beat bit munging except for small windows, until you get into SIMD solutions.
So they are data dependencies and not control ones. There are still some control ones.
Beyond that, let me be super clear: Imagine the following six versions:
1. One window at a time processing. No early exit, no bit munging.
2. One window at a time processing. No early exit, bit munging.
3. One window at a time processing. You don't use direct bit munging, but you early exit the window when you hit the non-unique character, and skip the window forward to the first instance of that non-unique character.
IE given "hmma<something>", n=4, you early exit at the second m, and skip processing windows forward to right after the first m (since no window prior to that can be unique, as they will all hit the double m)
4. One window at a time processing, bit munging, same otherwise as #3
5. Sliding window processing, no bit munging
6. Sliding window processing, bit munging.
The speedup between the 1-2 vs 3-6 is much greater than 5 vs 6 and 3 vs 4.
You could probably make 3 pretty darn competitive with 6, and 4 could probably beat 6 with SIMD (IE processing multiple windows in parallel really fast, and maybe wasting work, vs guaranteeing you only do the minimum work to find a unique window)
You could roll your own perfect hash, but you would end up with a solution that looks almost identical to TFA. If you use a stdlib hash, you are going to be chasing pointers all over memory to do a single insert / lookup. De-referencing a single pointer not in cache costs 50 - 100 clock cycles on a modern system. By the time you do one insert, TFA will have XOR'd at least 32 chars into its bit mask. And your cache won't be as nice as in TFA, slowing you down even more.
Given the two scenarios: 1) bit munging, no early return 2) hash lookup, early return
I would guess scenario 1 wins until word size gets above ~256. And obviously, we can add an early return to scenario 1 to make it unquestionably the fastest.
If you use a bit mask, you allocate all the memory up front. In a set you allocate through runtime, but could just use set.add(char - 'a') for a similar memory bound. But both need to be able to store every unique element. They are both O(Unique), it just happens that 26 <= num_bits(u32).
def first_diff(s, n):
cnt = Counter()
for i, c in enumerate(s, 1):
cnt[c] += 1
if i > n:
top = s[i - n - 1]
cnt[top] -= 1
if cnt[top] == 0:
del cnt[top]
if len(cnt) == n:
return i members = [0]*len(alphabet)
for i in 0...input length:
members[input[i-window_size]] = 0 if bounds ok
members[input[i]] = 1
if sum(members) == window_size:
return i
Ie, it's undeniable that the final program works much faster, but the article should really be called "a smarter memoization trick."
https://github.com/timvisee/advent-of-code-2022/blob/master/...
Maybe a bit less neat in the binary sense, but definitely very fast.
Running time of O(MG)
Normally for a search algorithm the size of the alphabet is assumed to be constant.
http://underhanded-c.org/_page_id_16.html
x86 CPUs have a dedicated instruction to swap two registers, or a register with memory.
“ fn run(s: &[char], window_size: usize) -> usize { let mut set = 0u32; for i in 0..s.len() { // Turn on bits as they enter the window set ^= 1 << (s[i] as u32 - 'a' as u32);
// Turn off bits as they leave the window
if i >= window_size {
set ^= 1 << (s[i - window_size] as u32 - 'a' as u32);
}
// Check the current window and see if we're done
if set.count_ones() as usize == window_size {
return i + 1;
}
}
panic!("No unique window found"); 'a' - 'a' = 0, so take 1 and shift it left 0 times:
00000000000000000000000000000001 = 'a'
'b' - 'a' = 1, so take 1 and shift it left 1 time:
00000000000000000000000000000010 = 'b'
'c' - 'a' = 2, so take 1 and shift it left 2 times:
00000000000000000000000000000100 = 'c'
'Stuff' there is just any expression (to understand separately) that evaluates to the number of positions to shift; `<<` is the operator for bit-shifting (left, cf. `>>`).
In brief `(s[i - window_size] as u32 - 'a' as u32)` is finding the character that just left the window on the left, represented as a number, starting from 'a' as 0 so that all 26 fit inside 32 bit positions.
Using codepoints directly, there is overlap. 'f' ^ 'd' will give you the same bit pattern as 'b'. You could keep an xor value for each window size smaller than the full window but that effectively brings back the inner loop that using xor is avoiding and you could just use equality. With codepoints, there may be a solution similar to a bloom filter so efficiently determine whether a duplicate is possible but I've not thought through that fully.
If you can use a 128 bit bitmap for the same cost then you could indeed directly index by ASCII values.
You can also get rid of the 'if' on window size in the main loop by partially unrolling it and taking those cases (start and end of string) outside.
The trick is that XOR will leave the bit set if there is an odd number of occurrences, and the only way to have the bit count equal the window size is if every char is unique.
https://www.geeksforgeeks.org/largest-sum-contiguous-subarra...