SeniorCodeOccasionalNot answered yet
Find a substring that is a permutation of S in O(|T|)
Given a text T and a pattern S, find the first substring of T that is an anagram of S (same multiset of characters), and return its start index, or -1.
Requirements:
- O(|T|) time with a constant that does NOT depend on the alphabet size.
- The window has fixed length
|S|.
int findAnagram(const std::string& T, const std::string& S) {
// your code here
}Write the implementation.
Slide a window of length |S| over T and keep one counter of how many character-counts still mismatch the pattern. On each slide add the entering char and drop the leaving char, updating that counter in O(1). When it hits zero the window is an anagram. O(|T|), alphabet-independent.
- ✗Re-scanning the whole frequency array per window, making the constant depend on alphabet size
- ✗Forgetting to both add the entering and remove the leaving character on each slide
- ✗Confusing anagram (same multiset) with equality (same order)
- →How would you return all anagram start indices instead of the first?
- →Why does maintaining a single mismatch counter make the per-slide work O(1)?
Contents
Task
Find the first substring of T that is a permutation of S, in O(|T|).
Solution
int findAnagram(const std::string& T, const std::string& S) {
if (S.size() > T.size()) return -1;
std::array<int, 256> need{};
int mismatches = 0;
for (unsigned char c : S) { if (need[c]++ == 0) ++mismatches; }
auto add = [&](unsigned char c, int delta) {
if (need[c] == 0) ++mismatches;
need[c] -= delta;
if (need[c] == 0) --mismatches;
};
for (int i = 0; i < static_cast<int>(T.size()); ++i) {
add(T[i], 1);
if (i >= static_cast<int>(S.size())) add(T[i - S.size()], -1);
if (i >= static_cast<int>(S.size()) - 1 && mismatches == 0)
return i - static_cast<int>(S.size()) + 1;
}
return -1;
}Key points
- A fixed-length
|S|window adds the entering and removes the leaving character. - The mismatch counter updates in O(1), so the constant is alphabet-independent.
- An anagram is a multiset match, not an order match.
Contents
