Welcome to Subscribe On Youtube
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 <= 105sconsists of lowercase English letters
Solutions
-
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; } }; -
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 -
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; }