1358. Number of Substrings Containing All Three Characters

leetcode medium

#array#csharp#hash-table#leetcode#medium#sliding-window#string#tree

Task

Дана строка s, состоящая только из символов a, b и c.

Верните количество подстрок, содержащих хотя бы одно вхождение всех этих символов a, b и c.

Пример

Input: s = "abc"

Output: 1

C# solution

matched/original

public class Solution {
    public int NumberOfSubstrings(string s) {
        int count = 0;
        int[] charCount = new int[3];
        int i = 0;
        
        for (int j = 0; j < s.Length; j++) {
            charCount[s[j] - 'a']++;
            
            while (charCount[0] > 0 && charCount[1] > 0 && charCount[2] > 0) {
                count += s.Length - j;
                charCount[s[i] - 'a']--;
                i++;
            }
        }
        
        return count;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int NumberOfSubstrings(string s) {
        int count = 0;
        vector<int>& charCount = new int[3];
        int i = 0;
        
        for (int j = 0; j < s.size(); j++) {
            charCount[s[j] - 'a']++;
            
            while (charCount[0] > 0 && charCount[1] > 0 && charCount[2] > 0) {
                count += s.size() - j;
                charCount[s[i] - 'a']--;
                i++;
            }
        }
        
        return count;
    }
}

Java solution

matched/original

public class Solution {
    public int numberOfSubstrings(String s) {
        int count = 0;
        int[] charCount = new int[3];
        int i = 0;
        
        for (int j = 0; j < s.length(); j++) {
            charCount[s.charAt(j) - 'a']++;
            
            while (charCount[0] > 0 && charCount[1] > 0 && charCount[2] > 0) {
                count += s.length() - j;
                charCount[s.charAt(i) - 'a']--;
                i++;
            }
        }
        
        return count;
    }
}

JavaScript solution

matched/original

var numberOfSubstrings = function(s) {
    let count = 0;
    let charCount = { 'a': 0, 'b': 0, 'c': 0 };
    let i = 0;
    
    for (let j = 0; j < s.length; j++) {
        charCount[s[j]]++;
        
        while (charCount['a'] > 0 && charCount['b'] > 0 && charCount['c'] > 0) {
            count += s.length - j;
            charCount[s[i]]--;
            i++;
        }
    }
    
    return count;
};

Python solution

matched/original

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        count = 0
        char_count = {'a': 0, 'b': 0, 'c': 0}
        i = 0
        
        for j in range(len(s)):
            char_count[s[j]] += 1
            
            while all(char_count[char] > 0 for char in "abc"):
                count += len(s) - j
                char_count[s[i]] -= 1
                i += 1
        
        return count

Explanation

Algorithm

Инициализация указателей и счетчиков:

Создайте три указателя i, j, и count для отслеживания текущего положения в строке и подсчета подстрок. Используйте словарь для подсчета вхождений символов a, b, и c.

Расширение окна:

Перемещайте правый указатель j по строке и увеличивайте счетчики символов в словаре. Как только все три символа (a, b, и c) присутствуют в текущем окне, начинайте уменьшать левый указатель i.

Уменьшение окна и подсчет подстрок:

Для каждого сдвига i вправо, проверяйте наличие всех символов в текущем окне. Если все символы присутствуют, добавьте количество подстрок, заканчивающихся в позиции j, к общему счету. Сдвигайте i вправо до тех пор, пока условие выполнения не нарушится.

Верните итоговое количество подстрок.

😎