Number of Substrings with at least 3 characters

XXX. Count Substrings Containing All Three Characters

String

Sliding Window

Problem Statement:

Given a string s consisting of characters 'a', 'b', and 'c', return the number of substrings that contain at least one occurrence of all three characters.

• Substrings may overlap
• Each valid substring should be counted
• String only contains lowercase a, b, and c

Algorithm:

1. **Window Management**:
   • Use sliding window to track character counts
   • Expand window until all characters present
   • Contract window from left while maintaining validity
2. **Counting Strategy**:
   • For each end position, count all valid starting positions
   • Number of valid starts equals left pointer position
   • Add this count to total result

Complexity:

Time Complexity: O(n), where n is string length
Space Complexity: O(1), fixed size array for counts

Implementation:

Java Solution:

public int numberOfSubstrings(String s) {
    int[] count = {0, 0, 0};                    // Count of a, b, c
    int res = 0, i = 0, n = s.length();         // i is left pointer
    
    for (int j = 0; j < n; ++j) {               // j is right pointer
        ++count[s.charAt(j) - 'a'];             // Add new character
        
        while (count[0] > 0 && count[1] > 0 && count[2] > 0)
            --count[s.charAt(i++) - 'a'];       // Remove chars from left
        
        res += i;                               // Add count of valid starts
    }
    return res;
}
                

Python Solution:

def numberOfSubstrings(self, s: str) -> int:
    count = [0, 0, 0]                          # Count of a, b, c
    res = i = 0                                # i is left pointer
    n = len(s)
    
    for j in range(n):                         # j is right pointer
        count[ord(s[j]) - ord('a')] += 1       # Add new character
        
        while all(c > 0 for c in count):       # While all chars present
            count[ord(s[i]) - ord('a')] -= 1   # Remove chars from left
            i += 1
            
        res += i                               # Add count of valid starts
    
    return res
                

C++ Solution:

int numberOfSubstrings(string s) {
    vector count(3);                      // Count of a, b, c
    int res = 0, i = 0, n = s.length();       // i is left pointer
    
    for (int j = 0; j < n; ++j) {             // j is right pointer
        ++count[s[j] - 'a'];                  // Add new character
        
        while (count[0] > 0 && count[1] > 0 && count[2] > 0)
            --count[s[i++] - 'a'];            // Remove chars from left
            
        res += i;                             // Add count of valid starts
    }
    return res;
}
                

Explanation:

• **Window Logic**:
  • Right pointer adds characters to window
  • Left pointer shrinks window when valid
  • Maintain minimal window with all characters
• **Counting Logic**:
  • Left pointer position indicates valid starting points
  • All positions left of i can start valid substring
  • Current position j is the ending point
• **Key Insights**:
  • Window shrinks to minimum valid size
  • All substrings ending at j and starting before i are valid
  • Count array tracks character frequencies