2743. 计算没有重复字符的子字符串数量 🔒 |
您所在的位置：网站首页 › 字符串字母数量 › 2743. 计算没有重复字符的子字符串数量 🔒 |
2743. 计算没有重复字符的子字符串数量 🔒
|
2743. 计算没有重复字符的子字符串数量 🔒
给定你一个只包含小写英文字母的字符串 s 。如果一个子字符串不包含任何字符至少出现两次（换句话说，它不包含重复字符），则称其为 特殊 子字符串。你的任务是计算 特殊 子字符串的数量。例如，在字符串 "pop" 中，子串 "po" 是一个特殊子字符串，然而 "pop" 不是 特殊 子字符串（因为 'p' 出现了两次）。 返回 特殊 子字符串的数量。 子字符串 是指字符串中连续的字符序列。例如，"abc" 是 "abcd" 的一个子字符串，但 "acd" 不是。
示例 1： 输入：s = "abcd" 输出：10 解释：由于每个字符只出现一次，每个子串都是特殊子串。长度为 1 的子串有 4 个，长度为 2 的有 3 个，长度为 3 的有 2 个，长度为 4 的有 1 个。所以一共有 4 + 3 + 2 + 1 = 10 个特殊子串。示例 2： 输入：s = "ooo" 输出：3 解释：任何长度至少为 2 的子串都包含重复字符。所以我们要计算长度为 1 的子串的数量，即 3 个。示例 3： 输入：s = "abab" 输出：7 解释：特殊子串如下（按起始位置排序）： 长度为 1 的特殊子串："a", "b", "a", "b" 长度为 2 的特殊子串："ab", "ba", "ab" 并且可以证明没有长度至少为 3 的特殊子串。所以答案是4 + 3 = 7。
提示： 1 1: cnt[s[j]] -= 1 j += 1 ans += i - j + 1 return ans 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16class 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 1) { --cnt[s.charAt(j++) - 'a']; } ans += i - j + 1; } return ans; } } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17class Solution { public: int numberOfSpecialSubstrings(string s) { int n = s.size(); int cnt[26]{}; int ans = 0; for (int i = 0, j = 0; i 1) { --cnt[s[j++] - 'a']; } ans += i - j + 1; } return ans; } }; 1 2 3 4 5 6 7 8 9 10 11 12 13 14func 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 } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15function 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 1) { --cnt[idx(s[j++])]; } ans += i - j + 1; } return ans; } GitHub 评论 |
【本文地址】
今日新闻 |
推荐新闻 |