Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

One can improve this even further I think. First, using an iterator instead of indexing into an UTF-8 string. Second, using the codepoint value directly as a bitmask (why is author realigning the bit mask to "a" in the first place?)


I assume the author is realigning to get only one bit for each letter. This relies on having an alphabet of 26 characters where 26 is less than the 32 available in a u32. In most real-world problems, you need to allow for the full ASCII or Unicode range and this wouldn't be possible.

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.


You are right. Total brainfart on my side. I skimmed the article too fast and completely misunderstood the approach.


The author passed the input as &[char] not &str, so indexing is no problem. That's weird in its own right, but obviously not the core of the post.


Looking at ASCII decimal values, a-z correspond to 97-122 so if you want to use a 32 bit bitmap you remap 97-122 to 0-25 by subtracting 97 ('a').

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 point is that each character represents a single bit in the mask, so it's easy to count the whole number of characters using popcount. If you XOR in the characters directly you can no longer easily count which characters are in the set.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: