Skip to content

feat: update solutions to lc problems: No.1100,1852 #2569

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 1 commit into from
Apr 11, 2024
Merged

feat: update solutions to lc problems: No.1100,1852 #2569

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
220 changes: 72 additions & 148 deletions ...n/1100-1199/1100.Find K-Length Substrings With No Repeated Characters/README.md
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -39,52 +39,52 @@

## 解法

### 方法一：双指针 + 计数器
### 方法一：滑动窗口 + 哈希表

我们观察发现，字符均为小写字母，也即最多有 $26$ 种不同的字符。因此，如果 $k \gt 26$ 或者 $k \gt n$，则无法找到任何长度为 $k$ 且不含重复字符的子串，直接返回 $0$ 即可。
我们维护一个长度为 $k$ 的滑动窗口，用一个哈希表 $cnt$ 统计窗口中每个字符的出现次数。

接下来，我们用双指针 $j$ 和 $i$ 维护一个滑动窗口，其中 $j$ 是滑动窗口的左端点，$i$ 是滑动窗口的右端点，用一个计数器 $cnt$ 统计滑动窗口中每个字符出现的次数。
首先，我们将字符串 $s$ 的前 $k$ 个字符加入哈希表 $cnt$ 中，并判断 $cnt$ 的大小是否等于 $k$，如果等于 $k$，则说明窗口中的字符都不相同，答案 $ans$ 加一。

遍历字符串 $s$，每次将 $s[i]$ 加入滑动窗口，即 $cnt[s[i]]++$，如果此时 $cnt[s[i]] \gt 1$ 或者 $i - j + 1 \gt k$，则循环将 $s[j]$ 从滑动窗口中移除，即 $cnt[s[j]]--$，并将 $j$ 右移。如果 $j$ 右移结束后，窗口大小 $i - j + 1$ 恰好等于 $k$，则说明滑动窗口中的字符串是一个符合题意的子串，将结果加一。
接下来，我们从 $k$ 开始遍历字符串 $s$，每次将 $s[i]$ 加入哈希表 $cnt$ 中，同时将 $s[i-k]$ 从哈希表 $cnt$ 中减一，如果 $cnt[s[i-k]]$ 减一后等于 $0$，则将 $s[i-k]$ 从哈希表 $cnt$ 中删除。如果此时哈希表 $cnt$ 的大小等于 $k$，则说明窗口中的字符都不相同，答案 $ans$ 加一。

遍历结束后，即可得到所有符合题意的子串的个数。
最后，返回答案 $ans$ 即可。

时间复杂度 $O(n)$，空间复杂度 $O(C)$。其中 $n$ 为字符串 $s$ 的长度；而 $C$ 为字符集的大小，本题中 $C = 26$。
时间复杂度 $O(n)$，空间复杂度 $O(\min(k, |\Sigma|))$，其中 $n$ 为字符串 $s$ 的长度；而 $\Sigma$ 为字符集，本题中字符集为小写英文字母，所以 $|\Sigma| = 26$。

<!-- tabs:start -->

```python
class Solution:
def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
n = len(s)
if k > n or k > 26:
return 0
ans = j = 0
cnt = Counter()
for i, c in enumerate(s):
cnt[c] += 1
while cnt[c] > 1 or i - j + 1 > k:
cnt[s[j]] -= 1
j += 1
ans += i - j + 1 == k
cnt = Counter(s[:k])
ans = int(len(cnt) == k)
for i in range(k, len(s)):
cnt[s[i]] += 1
cnt[s[i - k]] -= 1
if cnt[s[i - k]] == 0:
cnt.pop(s[i - k])
ans += int(len(cnt) == k)
return ans
```

```java
class Solution {
public int numKLenSubstrNoRepeats(String s, int k) {
int n = s.length();
if (k > n || k > 26) {
if (n < k) {
return 0;
}
int[] cnt = new int[128];
int ans = 0;
for (int i = 0, j = 0; i < n; ++i) {
++cnt[s.charAt(i)];
while (cnt[s.charAt(i)] > 1 || i - j + 1 > k) {
cnt[s.charAt(j++)]--;
Map<Character, Integer> cnt = new HashMap<>(k);
for (int i = 0; i < k; ++i) {
cnt.merge(s.charAt(i), 1, Integer::sum);
}
int ans = cnt.size() == k ? 1 : 0;
for (int i = k; i < n; ++i) {
cnt.merge(s.charAt(i), 1, Integer::sum);
if (cnt.merge(s.charAt(i - k), -1, Integer::sum) == 0) {
cnt.remove(s.charAt(i - k));
}
ans += i - j + 1 == k ? 1 : 0;
ans += cnt.size() == k ? 1 : 0;
}
return ans;
}
Expand All @@ -96,17 +96,20 @@ class Solution {
public:
int numKLenSubstrNoRepeats(string s, int k) {
int n = s.size();
if (k > n || k > 26) {
if (n < k) {
return 0;
}
int cnt[128]{};
int ans = 0;
for (int i = 0, j = 0; i < n; ++i) {
unordered_map<char, int> cnt;
for (int i = 0; i < k; ++i) {
++cnt[s[i]];
}
int ans = cnt.size() == k;
for (int i = k; i < n; ++i) {
++cnt[s[i]];
while (cnt[s[i]] > 1 || i - j + 1 > k) {
--cnt[s[j++]];
if (--cnt[s[i - k]] == 0) {
cnt.erase(s[i - k]);
}
ans += i - j + 1 == k;
ans += cnt.size() == k;
}
return ans;
}
Expand All @@ -115,17 +118,24 @@ public:

```go
func numKLenSubstrNoRepeats(s string, k int) (ans int) {
if k > len(s) || k > 26 {
return 0
n := len(s)
if n < k {
return
}
cnt := map[byte]int{}
for i := 0; i < k; i++ {
cnt[s[i]]++
}
if len(cnt) == k {
ans++
}
cnt := [128]int{}
for i, j := 0, 0; i < len(s); i++ {
for i := k; i < n; i++ {
cnt[s[i]]++
for cnt[s[i]] > 1 || i-j+1 > k {
cnt[s[j]]--
j++
cnt[s[i-k]]--
if cnt[s[i-k]] == 0 {
delete(cnt, s[i-k])
}
if i-j+1 == k {
if len(cnt) == k {
ans++
}
}
Expand All @@ -136,7 +146,7 @@ func numKLenSubstrNoRepeats(s string, k int) (ans int) {
```ts
function numKLenSubstrNoRepeats(s: string, k: number): number {
const n = s.length;
if (k > n) {
if (n < k) {
return 0;
}
const cnt: Map<string, number> = new Map();
Expand Down Expand Up @@ -164,120 +174,34 @@ class Solution {
* @return Integer
*/
function numKLenSubstrNoRepeats($s, $k) {
$sum = ($k * ($k + 1)) / 2 - $k;
$cnt = $tmp = 0;
for ($i = 0; $i < strlen($s) - $k + 1; $i++) {
$str = substr($s, $i, $k);
for ($j = 0; $j < $k; $j++) {
$tmp += strpos($str, $str[$j]);
}
if ($tmp === $sum) {
$cnt++;
}
$tmp = 0;
}
return $cnt;
}
}
```

<!-- tabs:end -->

### 方法二

<!-- tabs:start -->

```python
class Solution:
def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
n = len(s)
if k > n:
return 0
cnt = Counter(s[:k])
ans = int(len(cnt) == k)
for i in range(k, n):
cnt[s[i]] += 1
cnt[s[i - k]] -= 1
if cnt[s[i - k]] == 0:
cnt.pop(s[i - k])
ans += len(cnt) == k
return ans
```

```java
class Solution {
public int numKLenSubstrNoRepeats(String s, int k) {
int n = s.length();
if (k > n) {
$n = strlen($s);
if ($n < $k) {
return 0;
}
Map<Character, Integer> cnt = new HashMap<>(k);
for (int i = 0; i < k; ++i) {
cnt.merge(s.charAt(i), 1, Integer::sum);
}
int ans = cnt.size() == k ? 1 : 0;
for (int i = k; i < n; ++i) {
cnt.merge(s.charAt(i), 1, Integer::sum);
if (cnt.merge(s.charAt(i - k), -1, Integer::sum) == 0) {
cnt.remove(s.charAt(i - k));
$cnt = [];
for ($i = 0; $i < $k; ++$i) {
if (!isset($cnt[$s[$i]])) {
$cnt[$s[$i]] = 1;
} else {
$cnt[$s[$i]]++;
}
ans += cnt.size() == k ? 1 : 0;
}
return ans;
}
}
```

```cpp
class Solution {
public:
int numKLenSubstrNoRepeats(string s, int k) {
int n = s.size();
if (k > n) {
return 0;
}
unordered_map<char, int> cnt;
for (int i = 0; i < k; ++i) {
cnt[s[i]]++;
}
int ans = cnt.size() == k ? 1 : 0;
for (int i = k; i < n; ++i) {
cnt[s[i]]++;
cnt[s[i - k]]--;
if (cnt[s[i - k]] == 0) {
cnt.erase(s[i - k]);
$ans = count($cnt) == $k ? 1 : 0;
for ($i = $k; $i < $n; ++$i) {
if (!isset($cnt[$s[$i]])) {
$cnt[$s[$i]] = 1;
} else {
$cnt[$s[$i]]++;
}
ans += cnt.size() == k ? 1 : 0;
if ($cnt[$s[$i - $k]] - 1 == 0) {
unset($cnt[$s[$i - $k]]);
} else {
$cnt[$s[$i - $k]]--;
}
$ans += count($cnt) == $k ? 1 : 0;
}
return ans;
return $ans;
}
};
```

```go
func numKLenSubstrNoRepeats(s string, k int) (ans int) {
n := len(s)
if k > n {
return 0
}
cnt := map[byte]int{}
for i := 0; i < k; i++ {
cnt[s[i]]++
}
if len(cnt) == k {
ans++
}
for i := k; i < n; i++ {
cnt[s[i]]++
cnt[s[i-k]]--
if cnt[s[i-k]] == 0 {
delete(cnt, s[i-k])
}
if len(cnt) == k {
ans++
}
}
return
}
```

Expand Down
Loading