567: Permutation in String

Question

I implemented a solution to the LeetCode problem: 567. Permutation in String

The Problem

Given two strings s1(queryStr) and s2(sourceStr), return true if s2 contains a permutation of s1, or false otherwise.In other words, return true if one of s1's permutations is a substring of s2.

I had 3 goals in mind:

1. Make it as readable as possible, as if I were doing this at work (we prioritize readability over the typical 1-letter-variable nonsense you see in LeetCode submissions).
2. It needs to still be fast.
3. If it's slow, learn why and optimize.

For my algorithm, I ended up using the sliding window method. If you're unfamiliar with that, basically you keep track of a "window" of letters you can actually see. You check if that window is a permutation, and then if not you just slide it up by 1.

The algorithm

// establish the initial window and set up lookup tables // queryStr = abbo // sourceStr = beidbabooo // windowEnd | // windowBegin _ // store the frequencey of letters both queryStr and sourceStr in lookup tables // the window is a permutation of queryString when both lookup tables are identical if beid is a permutation of abbo done else while not done // Each time we move the window, we only update the character // that fell off, and the new one we can now see. move window if window is a permutation of queryString done 

The code

NOTE: You can download the code here in case you'd like to run my tests: code . I will also place my test cases here, just know that you won't be able to run it unless you have Catch2, or just download my .sln and press build.

main.cpp

 // uncomment these to enable test cases. // #define CATCH_CONFIG_MAIN // #include "Catch2/catch.hpp" #include "common/Log.h" #include "common/Random.h" #include "common/Timer.h" #include <algorithm> #include <assert.h> #include <fstream> #include <random> #include <string> #include <string_view> #include <iostream> #include <iterator> namespace { // Used to index lowercase ascii characters. int s_letterOffset = 97; int s_asciiTableSize = 26; // Frequency of all chars in the string we want permutations of. std::vector<int> s_queryStrFrequencyTable(s_asciiTableSize, 0); // Frequency of all chars in the string that might contain permutations of query. std::vector<int> s_sourceStrFrequencyTable(s_asciiTableSize, 0); } struct Window { // Index into source string of the first character in the window. int beginIndex = 0; // Keeping track of the number of matches we find in our window. int numMatches = 0; // View of the letters we can see through the window. std::string_view view; }; void IncrementFrequency(std::vector<int>& table, char letter) { // index into the table using ascii as an index. table[letter - s_letterOffset]++; } void DecrementFrequency(std::vector<int>& table, char letter) { // index into the table using ascii as an index. int count = table[letter - s_letterOffset]; count--; // This should never be below 0. assert(count >= 0); table[letter - s_letterOffset] = count; } // returns whether the letter appears in both tables. bool isMatch(char letter) { return s_queryStrFrequencyTable[letter - s_letterOffset] > 0 && s_sourceStrFrequencyTable[letter - s_letterOffset] > 0; } bool isFrequencyMatch(char letter) { return s_queryStrFrequencyTable[letter - s_letterOffset] == s_sourceStrFrequencyTable[letter - s_letterOffset]; } void init(const std::string queryStr, const std::string& sourceStr, Window& window) { std::fill(std::begin(s_queryStrFrequencyTable), std::end(s_queryStrFrequencyTable), 0); std::fill(std::begin(s_sourceStrFrequencyTable), std::end(s_sourceStrFrequencyTable), 0); // Init the window. window.beginIndex = 0; std::string_view view(sourceStr.data(), queryStr.size()); // Populate initial frequency table for query string. for (int i = 0; i < queryStr.size(); ++i) { IncrementFrequency(s_queryStrFrequencyTable, queryStr[i]); } // Load the initial window into the source frequency table. for (int i = 0; i < view.size(); ++i) { IncrementFrequency(s_sourceStrFrequencyTable, sourceStr[i]); } // Init matches in our inital window. for (int i = 0; i < view.size(); ++i) { if (isMatch(view[i])) { window.numMatches++; } } window.view = view; } // Moves the window forward one step void updateWindow(Window& window, const std::string& sourceStr) { // To move the window, we need to shift the left side and then the right. std::string_view& view = window.view; // We need to account for matches that might have fallen out of view. if (isMatch(view[0])) { window.numMatches--; } DecrementFrequency(s_sourceStrFrequencyTable, view[0]); // Shift the window over. window.beginIndex++; view = std::string_view(sourceStr.data() + window.beginIndex, view.size()); int viewEnd = view.size() - 1; IncrementFrequency(s_sourceStrFrequencyTable, view[viewEnd]); // Now we need to account for any new matches that might have come into view. if (isMatch(view[viewEnd])) { window.numMatches++; } } bool IsWindowPermutation(const Window& window) { const std::string_view& windowView = window.view; int viewSize = windowView.size(); if (window.numMatches != viewSize) { return false; } // If all characters in our view are matches of the same frequency, // this window is a permutation. bool isPermutation = true; for (int i = 0; i < viewSize; ++i) { isPermutation &= isMatch(windowView[i]) && isFrequencyMatch(windowView[i]); } return isPermutation; } bool checkInclusion(std::string queryStr, std::string sourceStr) { // There are not enough letters in sourceStr to contain a permutation of queryStr. if (queryStr.size() > sourceStr.size()) { return false; } Window window; // Set up the look up tables and our initial window.s init(queryStr, sourceStr, window); // We're done if window happens to be a permutation. if (IsWindowPermutation(window)) { return true; } int sentinal = sourceStr.size() - queryStr.size(); while (window.beginIndex < sentinal) { // Move the window and check if that's a permutation. updateWindow(window, sourceStr); if (IsWindowPermutation(window)) { return true; } } return false; } 

The test cases:

SCENARIO("Determine if a string contains a permutation of another string.") { GIVEN("test string [abbo] source string [beidbabooo]") { std::string s1 = "abbo"; std::string s2 = "beidbabooo"; WHEN("Searching for permutation") { REQUIRE(checkInclusion(s1, s2) == true); } } GIVEN("test string with permutation at end") { std::string s1 = "ab"; std::string s2 = "lkjhgfdsaapoiuytrewba"; WHEN("Searching for permutation") { REQUIRE(checkInclusion(s1, s2) == true); } } GIVEN("test string with permutation at beginning") { std::string s1 = "ab"; std::string s2 = "bacdefghijku"; WHEN("Searching for permutation") { REQUIRE(checkInclusion(s1, s2) == true); } } GIVEN("test string with lots of duplicates") { std::string s1 = "ab"; std::string s2 = "aaaaaaaaaaaaaaaafbfafbfabfffaoksl"; WHEN("Searching for permutation") { REQUIRE(checkInclusion(s1, s2) == true); } } GIVEN("An source string larger than query string.") { std::string s1 = "ab"; std::string s2 = "a"; WHEN("Searching for permutation") { REQUIRE(checkInclusion(s1, s2) == false); } } GIVEN("Testing a massive string with permutation at end") { // Generate massive random string with guaranteed permutation at the end. //std::string s1 = "snroavitraifgtwrkchdczmlduoxpqkvbyftej"; ////std::string s1 = "aabbbcde"; //std::string s2 = Common::GetRandomLowercaseString(10000000); //std::stringstream ss; //ss << s2 << s1; //std::ofstream out("test_data.txt"); //out << ss.str(); //out.close(); //----------------------------------------------------------- std::ifstream data; data.open("test_data.txt"); std::string s1 = "aabccddeffghiijkklmnoopqrrrstttuvvwxyz"; //std::string s1 = "cadebabb"; std::string s2; s2.reserve(10000000); std::getline(data, s2); WHEN("Searching for permutation") { Common::Timer timer; timer.Start(); bool foundPermutation = checkInclusion(s1, s2); REQUIRE(foundPermutation); timer.Stop(); std::cout << fmt::format("Found permutation test 2: {} |Time Elapsed: {}ms\n", foundPermutation, timer.GetTotalElapsedMs().count()); } } } 

The results

Last test case tests a massive string where I've put a permutation manually at the back of it. Because the probability of randomly generating a large permutation of another string is so small, I've found this is sufficient to test "worst case scenario"

• queryString size = 38
  sourceStr size = 10⁸
  Average time to find permutation = 11832ms

• queryString size = 38
  sourceStr size = 10⁷
  Average time to find permutation = 1235ms

• queryString size = 38
  sourceStr size = 10⁶
  Average time to find permutation = 118ms

• queryString size = 38
  sourceStr size = 10⁴
  Average time to find permutation = 1ms

• queryString size = 8
  sourceStr size = 10⁸
  Average time to find permutation = 23ms

All of these test cases pass and the solution is accepted by LeetCode. But, according to LeetCode, my solution falls in the bottom 10% of solutions for CPU speed. And while their method of speed benchmarking is terrible, it's consistently at the bottom.

Attempting to diagnose the bottleneck

1. I've tried testing against a string with 1 billion letters in release and just pressing "pause" to see what function I end up in. Presumably, if there was a consistent bottleneck I would land in the same spot across multiple samples. But my break points were not consistently in the same function.

2. I tried running the Visual Studio profiler, and it says that updateWindow is doing 95% of the work. Which should be obvious. It won't let me drill down any further though so, kind of useless.

My question

What could be taking so long? I'm not allocating anything. The only thing I can think of is that I'm constructing a string_view very often but, that's just a pointer and an int. My code is literally just a bunch of boolean checks and int increments.

Is there something horribly inefficient that I'm overlooking?

Update

Given the data, its clear that time increases with the size of query string. This makes sense if you look at IsWindowPermutation. I'm iterating the size of window to check whether it is a permutation. This means for small windows it's very fast, but for larger windows it's slower.

So an optimization would be:

// if window.size > 26 for (int i = 0; i < s_asciiTableSize; ++i) { isPermutation &= s_queryStrFrequencyTable[i] == s_sourceStrFrequencyTable[i]; } 

This way, the maximum size we need to iterate is just the length of the alphabet. However, when I measured this optimization, even when window was size 26, the old method was still much much slower when I expected it to be the same.

The only thing I can think of is that in the old method, I'm subtracting an offset when indexing into the lookup tables. Measuring this operation:

// Method 1 //for (int i = 0; i < viewSize; ++i) //{ // s_timer.Start(); // isPermutation &= s_queryStrFrequencyTable[windowView[i] - s_letterOffset] // == s_sourceStrFrequencyTable[windowView[i] - s_letterOffset]; // s_timer.Stop(); // std::cout << fmt::format("indexing array with offset: |Time Elapsed: {}ns\n", // s_timer.GetTotalElapsedNs().count()); //} // Method 2 for (int i = 0; i < s_asciiTableSize; ++i) { s_timer.Start(); isPermutation &= s_queryStrFrequencyTable[i] == s_sourceStrFrequencyTable[i]; s_timer.Stop(); std::cout << fmt::format("indexing array: |Time Elapsed: {}ns\n", s_timer.GetTotalElapsedNs().count()); } 

Method 1 takes 100 nanoseconds to perform the each permutation check by indexing with an offset. Method 2 takes 0 - 100 nanoseconds.

Maybe indexing into array with the output of some arithmetic is super expensive? Either way I submitted this optimization to LeetCode and am now faster than 97% of all submissions. So, I'd call that good enough. I think the swings now are just going to be down to the way they measure speed which is notoriously inaccurate.

Answer 1

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.
Depending on the way you keep counts, you could conceivably swap in size of subset used in queryString.
The (achievable) goal is constant effort per shift.

---

Readability -
There's good, and there's bad.
I see descriptive names.
For the most part, name styling is consistent.

I see comments - most of them "in the code",
most avoiding common errors such as repeating what the statement "does".
(This should never be below 0 would seem to fail in this regard, but I usually type comments before typing statements.
And may end up with a similar coincidence.)

Two functions got a comment describing their purpose:
Make that a habit where the name doesn't tell it all.
Find a "documentation tool" turning special comments into a source code documentation (draft).

What you put in a separate block as describing The algorithm would be a valuable introduction in the code.
In fact, in its current state, IsWindowPermutation() would deserve a similar description of its own.

The biggest single hindrance I had while reading your code was that I was thinking of a simpler solution and had an aversion to the "unmotivated" introduction of things that I didn't think beneficial:
Why keep numMatches?
An explicit Window, at that?

• Keep it simple!
  use one collection of counts, one for "each character(code)" you still need to see:
  increment for every element of the queryString
            and every element leaving the window
  decrement for every element entering the window
  find a condition telling whether the contents in the window is a permutation
  find a way to update this with every shift

---

Odds and ends:

• use of a testing tool: excellent.
  I already mentioned documentation tools.
  There are (micro-)benchmarking frameworks.
  (My take: obtaining meaningful benchmarking results is hard
  rather than LeetCode doing particularly bad here.)
• the early out on IsWindowPermutation(window) is repeated without necessity
• while I hope std::string_view() takes constant time, it looks like one of those things that can ruin your score with some "online judge"

Answer 2

Improving performance

There are a few ways to improve performance. You already have the basic structure right:

1. Do a few quick checks to see if it's possible at all that there is a permutation in the string.
2. For every window position, do a quick check first to see if this could possibly be a permutation.
3. If it is indeed possible, do a full check.

In order to improve performance, the trick is to make each of these three steps as fast as possible, or avoid needing some of those steps at all. Counting frequencies is a possibility, but there are 26 possible letters in the alphabet, so just comparing complete frequency tables means having to iterate over all 26 letters. This is expensive if the window is small.

A possible improvement is to maintain two bitmasks (one for the query string and one for the window), that just check if a given character is present in a string (view). This only takes 26 bits, so fits in a 32-bit integer, which is very fast to manipulate and check against.

Another one that works well for the sliding window is to just look at the sum of the ASCII values of the characters in the window. If it doesn't match the sum of the characters in the query string, you know it is not a match. And updating the sum when moving the window is very simple as well. Again this only needs two integers.

To do the full check, a frequency table approach is one way, but for small windows you might instead consider sorting the query string and the window, and then doing a simple string comparison between them.

Another possible improvement is to move the window by more than one character at a time. If you know that by comparing the window and the query string, it needs more than one character in the window changed to be able to match the query string, you can advance by two positions or perhaps even more, up to the size of the query string.

But in this case you can do even better. As greybeard mentioned, there is a way to cheaply update the frequency table of the window and compare it against the frequency table of the query string in \$O(1)\$ time. In fact, your code is already quite close to doing it with numMatches. Your "matches" just check that both frequency tables have a non-zero amount of a given letter. Instead, make it so it tracks the number of letters that have exactly the same frequency. If that number is equal to the number of unique letters in the query string, you have a match. Since updating this while shifting the window is very simple and \$O(1)\$, you probably don't need to do any other checks in order to get great performance.

Answer 3

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 tests where the function should return false. We definitely need one where the candidate substring is shorter than the population string, otherwise we could pass all the tests with a simple function:

bool checkInclusion(std::string_view queryStr, std::string_view sourceStr) { return queryStr.size() <= sourceStr.size(); } 

The final test (massive string) has a dependency on an external file. In my view, that's not a unit test. However, it's pretty simple to make it self-contained, because we can build the large string programmatically, perhaps by repeatedly writing into a std::stringstream.

Implementation

Missing include:

#include <vector> 

Unused includes (perhaps should move to the test code):

#include "common/Log.h" #include "common/Random.h" #include "common/Timer.h" #include <algorithm> #include <fstream> #include <iterator> #include <random> 

We seem to have assumed that input is encoded using ASCII. I don't see anything to justify that assumption, and would normally expect input to be in the host character coding. This dependency on ASCII is an unnecessary non-portability.

Avoid global variables - the frequency tables are data that should be private to each run of the function. It probably makes sense for Window to include these. Consider using std::array instead of std::vector.

We have a whole load of helper functions with external linkage. As this is supposed to be reusable production code, give them internal linkage (using static, or anonymous namespace).

We pass a lot of strings by value. Pass a reference to constant string - or better, a std::string_view (by value).

There's a lot of unnecessary implicit conversion between signed and unsigned integer types. For instance: for (int i = 0; i < queryStr.size(); ++i). We can simply change i to be a std::size_t and eliminate a warning (if you're not getting warnings for these, you really should enable them).

Instead of view[0] and view[viewEnd], we can simply (and more clearly) use the views front() and back().

---

I don't see the point of having both isMatch and isFrequencyMatch, and it's not clear which of these values numMatches is tracking.

A simpler version just tracks how many of our window's frequency bins have the same count as the query's frequency bins. When we advance the window, we add one to the count if ++window_count[view.back()] is equal to query_count[view.back()] and subtract one if window_count[view_front()]-- is equal to query_count[view.front()].

When the match count is the same as query_count.size(), we can return true. Then there's no need for the loop in IsWindowPermutation() (or for that even to be a function).

Minor

Naming: mix of camelCase and PascalCase for function names. Please be more consistent.

Spelling: sentinel, not sentinal. And frequency, not frequencey, in the initial comment (yes, comment spelling can matter when we grep a codebase!)