1358. Number of Substrings Containing All Three Characters

Description

Given a string s consisting only of characters a, b and c.

Return the number of substrings containing at least one occurrence of all these characters a, b and c.

Example 1:

Input: s = "abcabc"
Output: 10
Explanation: The substrings containing at least one occurrence of the characters a, b and c are "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" and "abc" (again).

Example 2:

Input: s = "aaacb"
Output: 3
Explanation: The substrings containing at least one occurrence of the characters a, b and c are "aaacb", "aacb" and "acb".

Example 3:

Input: s = "abc"
Output: 1

Constraints:

3 <= s.length <= 5 x 10⁴
s only consists of 'a', 'b' or 'c' characters.

Solutions

Solution 1: Single Pass

Thinking

Count substrings that contain \(a\), \(b\), and \(c\). \(n \le 5 \times 10^4\) rules out both endpoints. With right end \(i\), every left end at most the earliest of the three last-seen positions is valid. Tracking those three indices, we add \(\min(d[a],d[b],d[c])+1\) at each \(i\).

We use an array \(d\) of length \(3\) to record the most recent occurrence of the three characters, initially all set to \(-1\).

We traverse the string \(s\). For the current position \(i\), we first update \(d[s[i]]=i\), then the number of valid strings is \(\min(d[0], d[1], d[2]) + 1\), which is accumulated to the answer.

The time complexity is \(O(n)\), where \(n\) is the length of the string \(s\). The space complexity is \(O(1)\).

Python3JavaC++GoTypeScriptRust

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        d = {"a": -1, "b": -1, "c": -1}
        ans = 0
        for i, c in enumerate(s):
            d[c] = i
            ans += min(d["a"], d["b"], d["c"]) + 1
        return ans

class Solution {
    public int numberOfSubstrings(String s) {
        int[] d = new int[] {-1, -1, -1};
        int ans = 0;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            d[c - 'a'] = i;
            ans += Math.min(d[0], Math.min(d[1], d[2])) + 1;
        }
        return ans;
    }
}

class Solution {
public:
    int numberOfSubstrings(string s) {
        int d[3] = {-1, -1, -1};
        int ans = 0;
        for (int i = 0; i < s.size(); ++i) {
            d[s[i] - 'a'] = i;
            ans += min(d[0], min(d[1], d[2])) + 1;
        }
        return ans;
    }
};

func numberOfSubstrings(s string) (ans int) {
    d := [3]int{-1, -1, -1}
    for i, c := range s {
        d[c-'a'] = i
        ans += min(d[0], min(d[1], d[2])) + 1
    }
    return
}

function numberOfSubstrings(s: string): number {
    const d: number[] = [-1, -1, -1];
    let ans = 0;

    for (let i = 0; i < s.length; i++) {
        const c = s.charCodeAt(i) - 97;
        d[c] = i;

        ans += Math.min(d[0], Math.min(d[1], d[2])) + 1;
    }

    return ans;
}

impl Solution {
    pub fn number_of_substrings(s: String) -> i32 {
        let bytes = s.as_bytes();
        let mut d = [-1i32; 3];
        let mut ans: i32 = 0;

        for i in 0..bytes.len() {
            let c = (bytes[i] - b'a') as usize;
            d[c] = i as i32;

            let mn = d[0].min(d[1]).min(d[2]);
            ans += mn + 1;
        }

        ans
    }
}

Solution 2: Sliding Window

Thinking

The first method uses last-seen indices. A counting window works as well: after extending \(r\), shrink \(l\) while all three letters remain, then add the current \(l\) as the number of valid left ends. Both are linear; the window never stores last positions.

We can solve this using a sliding window. Maintain a window \([l, r]\) and an array \(\textit{cnt}\) recording the frequency of each character in the window.

Traverse the string and keep moving the right boundary \(r\) to include \(s[r]\). If the window contains at least one \(a\), \(b\), and \(c\), keep moving the left boundary \(l\) to the right until the window no longer contains all three characters.

At this point, all substrings ending at \(r\) that contain \(a\), \(b\), and \(c\) can start at indices \(0, 1, \ldots, l - 1\), giving \(l\) valid substrings in total. Add this count to the answer.

The time complexity is \(O(n)\), where \(n\) is the length of the string \(s\). The space complexity is \(O(1)\).

Python3JavaC++GoTypeScriptRust

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        ans = l = 0
        cnt = Counter()
        for r, c in enumerate(s):
            cnt[c] += 1
            while cnt['a'] and cnt['b'] and cnt['c']:
                cnt[s[l]] -= 1
                l += 1
            ans += l
        return ans

class Solution {
    public int numberOfSubstrings(String s) {
        int ans = 0, l = 0;
        int[] cnt = new int[3];
        for (int r = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            cnt[c - 'a']++;
            while (cnt[0] > 0 && cnt[1] > 0 && cnt[2] > 0) {
                cnt[s.charAt(l) - 'a']--;
                l++;
            }
            ans += l;
        }
        return ans;
    }
}

class Solution {
public:
    int numberOfSubstrings(string s) {
        int ans = 0, l = 0;
        int cnt[3] = {0, 0, 0};
        for (int r = 0; r < (int) s.size(); r++) {
            cnt[s[r] - 'a']++;
            while (cnt[0] && cnt[1] && cnt[2]) {
                cnt[s[l] - 'a']--;
                l++;
            }
            ans += l;
        }
        return ans;
    }
};

func numberOfSubstrings(s string) int {
    ans, l := 0, 0
    cnt := [3]int{}

    for r := 0; r < len(s); r++ {
        cnt[s[r]-'a']++

        for cnt[0] > 0 && cnt[1] > 0 && cnt[2] > 0 {
            cnt[s[l]-'a']--
            l++
        }

        ans += l
    }

    return ans
}

function numberOfSubstrings(s: string): number {
    let ans = 0,
        l = 0;
    const cnt = [0, 0, 0];

    for (let r = 0; r < s.length; r++) {
        cnt[s.charCodeAt(r) - 97]++;

        while (cnt[0] > 0 && cnt[1] > 0 && cnt[2] > 0) {
            cnt[s.charCodeAt(l) - 97]--;
            l++;
        }

        ans += l;
    }

    return ans;
}

impl Solution {
    pub fn number_of_substrings(s: String) -> i32 {
        let bytes = s.as_bytes();
        let mut ans = 0;
        let mut l = 0;
        let mut cnt = [0; 3];

        for r in 0..bytes.len() {
            cnt[(bytes[r] - b'a') as usize] += 1;

            while cnt[0] > 0 && cnt[1] > 0 && cnt[2] > 0 {
                cnt[(bytes[l] - b'a') as usize] -= 1;
                l += 1;
            }

            ans += l as i32;
        }

        ans
    }
}

1358. Number of Substrings Containing All Three Characters

Description

Solutions

Solution 1: Single Pass

Solution 2: Sliding Window

Comments