Count Substrings Without Repeating Character

Problem

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 ofspecial substrings.

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

Examples

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^5
• s consists of lowercase English letters

Solution

Method 1 – Sliding Window (Two Pointers)

Intuition

A substring without repeating characters is a substring where all characters are unique. For each position, we can use a sliding window to expand as far as possible to the right without repeating any character, and count all such substrings efficiently.

Approach

1. Use two pointers, l and r, to represent the current window.
2. Use a set or array to keep track of characters in the current window.
3. For each left pointer l, move the right pointer r as far as possible to the right such that all characters in s[l..r] are unique.
4. For each l, the number of special substrings starting at l is r - l.
5. Move l forward, removing s[l] from the set/array.
6. Sum up the counts for all l.

Code

C++

class Solution {
public:
    long long countSpecialSubstrings(string s) {
        int n = s.size();
        vector<int> last(26, -1);
        long long ans = 0;
        int l = 0;
        for (int r = 0; r < n; ++r) {
            l = max(l, last[s[r] - 'a'] + 1);
            ans += r - l + 1;
            last[s[r] - 'a'] = r;
        }
        return ans;
    }
};

Go

type Solution struct{}
func (Solution) CountSpecialSubstrings(s string) int64 {
    n := len(s)
    last := make([]int, 26)
    for i := range last {
        last[i] = -1
    }
    var ans int64
    l := 0
    for r := 0; r < n; r++ {
        if last[s[r]-'a']+1 > l {
            l = last[s[r]-'a'] + 1
        }
        ans += int64(r - l + 1)
        last[s[r]-'a'] = r
    }
    return ans
}

Java

class Solution {
    public long countSpecialSubstrings(String s) {
        int n = s.length();
        int[] last = new int[26];
        Arrays.fill(last, -1);
        long ans = 0;
        int l = 0;
        for (int r = 0; r < n; ++r) {
            l = Math.max(l, last[s.charAt(r) - 'a'] + 1);
            ans += r - l + 1;
            last[s.charAt(r) - 'a'] = r;
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun countSpecialSubstrings(s: String): Long {
        val n = s.length
        val last = IntArray(26) { -1 }
        var ans = 0L
        var l = 0
        for (r in 0 until n) {
            l = maxOf(l, last[s[r] - 'a'] + 1)
            ans += (r - l + 1)
            last[s[r] - 'a'] = r
        }
        return ans
    }
}

Python

class Solution:
    def countSpecialSubstrings(self, s: str) -> int:
        n = len(s)
        last = [-1] * 26
        ans = 0
        l = 0
        for r in range(n):
            l = max(l, last[ord(s[r]) - ord('a')] + 1)
            ans += r - l + 1
            last[ord(s[r]) - ord('a')] = r
        return ans

Rust

impl Solution {
    pub fn count_special_substrings(s: String) -> i64 {
        let n = s.len();
        let s = s.as_bytes();
        let mut last = vec![-1; 26];
        let mut ans = 0i64;
        let mut l = 0;
        for r in 0..n {
            l = l.max((last[(s[r] - b'a') as usize] + 1) as usize);
            ans += (r - l + 1) as i64;
            last[(s[r] - b'a') as usize] = r as i32;
        }
        ans
    }
}

TypeScript

class Solution {
    countSpecialSubstrings(s: string): number {
        const n = s.length;
        const last = Array(26).fill(-1);
        let ans = 0, l = 0;
        for (let r = 0; r < n; ++r) {
            l = Math.max(l, last[s.charCodeAt(r) - 97] + 1);
            ans += r - l + 1;
            last[s.charCodeAt(r) - 97] = r;
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n), where n is the length of s, since each character is processed at most twice.
• 🧺 Space complexity: O(1), only a fixed-size array is used.