2743. Count Substrings Without Repeating Character 🔒

Description

You are given a string s consisting only of lowercase English letters. We call a substring special if it contains no character which has occurred at least twice (in other words, it does not contain a repeating character). Your task is to count the number of special substrings. For example, in the string "pop", the substring "po" is a special substring, however, "pop" is not special (since 'p' has occurred twice).

Return the number of special substrings.

A substring is a contiguous sequence of characters within a string. For example, "abc" is a substring of "abcd", but "acd" is not.

Example 1:

Input: s = "abcd"
Output: 10
Explanation: Since each character occurs once, every substring is a special substring. We have 4 substrings of length one, 3 of length two, 2 of length three, and 1 substring of length four. So overall there are 4 + 3 + 2 + 1 = 10 special substrings.

Example 2:

Input: s = "ooo"
Output: 3
Explanation: Any substring with a length of at least two contains a repeating character. So we have to count the number of substrings of length one, which is 3.

Example 3:

Input: s = "abab"
Output: 7
Explanation: Special substrings are as follows (sorted by their start positions):
Special substrings of length 1: "a", "b", "a", "b"
Special substrings of length 2: "ab", "ba", "ab"
And it can be shown that there are no special substrings with a length of at least three. So the answer would be 4 + 3 = 7.

Constraints:

1 <= s.length <= 10⁵
s consists of lowercase English letters

Solutions

Solution 1: Counting + Two Pointers

We use two pointers \(j\) and \(i\) to represent the left and right boundaries of the current substring, and an array \(cnt\) of length \(26\) to count the occurrence of each character in the current substring. We traverse the string from left to right. Each time we traverse to position \(i\), we increase the occurrence of \(s[i]\), and then check whether \(s[i]\) appears at least twice. If so, we need to decrease the occurrence of \(s[j]\) and move \(j\) one step to the right, until the occurrence of \(s[i]\) does not exceed once. In this way, we get the length of the longest special substring ending with \(s[i]\), which is \(i - j + 1\), so the number of special substrings ending with \(s[i]\) is \(i - j + 1\). Finally, we add up the number of special substrings ending at each position to get the answer.

The time complexity is \(O(n)\), and the space complexity is \(O(C)\). Here, \(n\) is the length of the string \(s\), and \(C\) is the size of the character set. In this problem, the character set consists of lowercase English letters, so \(C = 26\).

Python3JavaC++GoTypeScript

class Solution:
    def numberOfSpecialSubstrings(self, s: str) -> int:
        cnt = Counter()
        ans = j = 0
        for i, c in enumerate(s):
            cnt[c] += 1
            while cnt[c] > 1:
                cnt[s[j]] -= 1
                j += 1
            ans += i - j + 1
        return ans

class Solution {
    public int numberOfSpecialSubstrings(String s) {
        int n = s.length();
        int ans = 0;
        int[] cnt = new int[26];
        for (int i = 0, j = 0; i < n; ++i) {
            int k = s.charAt(i) - 'a';
            ++cnt[k];
            while (cnt[k] > 1) {
                --cnt[s.charAt(j++) - 'a'];
            }
            ans += i - j + 1;
        }
        return ans;
    }
}

class Solution {
public:
    int numberOfSpecialSubstrings(string s) {
        int n = s.size();
        int cnt[26]{};
        int ans = 0;
        for (int i = 0, j = 0; i < n; ++i) {
            int k = s[i] - 'a';
            ++cnt[k];
            while (cnt[k] > 1) {
                --cnt[s[j++] - 'a'];
            }
            ans += i - j + 1;
        }
        return ans;
    }
};

func numberOfSpecialSubstrings(s string) (ans int) {
    j := 0
    cnt := [26]int{}
    for i, c := range s {
        k := c - 'a'
        cnt[k]++
        for cnt[k] > 1 {
            cnt[s[j]-'a']--
            j++
        }
        ans += i - j + 1
    }
    return
}

function numberOfSpecialSubstrings(s: string): number {
    const idx = (c: string) => c.charCodeAt(0) - 'a'.charCodeAt(0);
    const n = s.length;
    const cnt: number[] = Array(26).fill(0);
    let ans = 0;
    for (let i = 0, j = 0; i < n; ++i) {
        const k = idx(s[i]);
        ++cnt[k];
        while (cnt[k] > 1) {
            --cnt[idx(s[j++])];
        }
        ans += i - j + 1;
    }
    return ans;
}

2743. Count Substrings Without Repeating Character 🔒

Description

Solutions

Solution 1: Counting + Two Pointers

Comments