3 ms·
If the string is known to be in some specific alphabet (ie only lowercase a-z), you could use a 32-bit integer as an array of bools and toggle the individual bi
by WJW 5y ago
If the string is known to be in some specific alphabet (ie only lowercase a-z), you could use a 32-bit integer as an array of bools and toggle the individual bits between false and true. The final s.size() could be done with popcount(). Not even any sets needed.
(This type of stuff might fail the "overengineering" test that the grandparent comment talked about though.)
- loup-vaillant 5y agoWhether that's over-engineering or not really depends on the data. For this particular interview question we might assume we have very little data to process, but real applications might want to scale that to a point where you actually care about performance (MMO permutation palindrome checker or whatnot). Personally, I'd use the simplest implementation as a reference, and use it to test more optimised solutions if I ever need them.