MiddleCodeCommonNot answered yet
Count substrings with no repeating characters in O(n)
Given a string, count the pairs of indices (i, j) with i <= j such that the substring from i to j inclusive contains no repeated character. For "abd" the answer is 6.
Requirements:
- O(n) time, O(alphabet) extra memory.
- One pass; do not enumerate all substrings.
long long countDistinctSubstrings(const std::string& s) {
// your code here
}Write the implementation.
Sliding window: keep left as the start of the current repeat-free window and lastSeen[c] as each character's last index. For each right end j, set left = max(left, lastSeen[c]+1), then add j - left + 1 (the valid left ends) to the total. One pass, O(n).
- ✗Moving
lefttolastSeen[c]instead oflastSeen[c]+1, leaving the repeat inside the window - ✗Failing to clamp with
max(left, ...)soleftjumps backward on an old repeat - ✗Using
intfor the total when n is large enough to overflow
- →How does this differ from finding the length of the longest such substring?
- →Why must
leftonly ever move forward?
Contents
Task
Count pairs (i, j), i <= j, whose substring has no repeated character. For "abd" the answer is 6.
Solution
long long countDistinctSubstrings(const std::string& s) {
std::array<int, 256> lastSeen;
lastSeen.fill(-1);
long long total = 0;
int left = 0;
for (int j = 0; j < static_cast<int>(s.size()); ++j) {
unsigned char c = s[j];
if (lastSeen[c] >= left) left = lastSeen[c] + 1;
total += j - left + 1; // valid left ends
lastSeen[c] = j;
}
return total;
}Key points
- At each right end add the current repeat-free window length.
leftonly advances, giving O(n).lastSeen[c]+1excludes the repeat itself from the window.
Contents
