Count Substrings Without Repeating Character - CPP Solution

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++.