1. Introduction

This blog post focuses on a string processing problem that tests knowledge in C++ related to handling substrings and character uniqueness: counting the number of substrings without repeating characters. This problem is a classic example of using sliding window techniques for efficient string analysis.

Problem

Given a string, the goal is to count the number of substrings that contain no repeating characters.

2. Solution Steps

1. Use a sliding window approach to maintain a substring without repeating characters.

2. Create a set or hash map to keep track of the characters in the current window.

3. Iterate through the string, expanding the window by adding characters to the right.

4. If a character repeats, shrink the window from the left until the character is no longer in the window.

5. Count each valid window as a substring without repeating characters.

6. Continue until the end of the string and return the count.

3. Code Program

``````#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

// Function to count substrings without repeating characters
int countNonRepeatingSubstrs(string s) {
unordered_set<char> seen;
int left = 0, count = 0;

for (int right = 0; right < s.length(); right++) {
// Expand the window
while (seen.find(s[right]) != seen.end()) {
// Shrink the window from the left
seen.erase(s[left++]);
}
seen.insert(s[right]);

// Count the number of substrings ending at 'right'
count += right - left + 1;
}
return count;
}

int main() {
string s = "abcabcbb";
cout << "Number of non-repeating substrings: " << countNonRepeatingSubstrs(s) << endl;
return 0;
}
``````

Output:

```Number of non-repeating substrings: 22
```

Explanation:

1. The input string "abcabcbb" is processed to find substrings without repeating characters.

2. A sliding window is used to maintain a substring with unique characters.

3. The window expands by adding characters from the right and shrinks from the left when a repeating character is found.

4. Each valid window represents a unique substring, and the number of such substrings ending at each position is counted.

5. The total count of 22 indicates the number of non-repeating substrings in the input string.

6. This method efficiently utilizes the sliding window technique for substring analysis in C++.