資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中最多包含 K 個不同字元的最長子字串
假設我們有一個字串；我們需要計算包含最多 k 個不同字元的最長子字串 T 的長度。
因此，如果輸入類似於 s = "eceba"，k = 2，則輸出將為 3，因為 T 是 "ece"，其長度為 3。
為了解決這個問題，我們將遵循以下步驟：
ans := 0
定義一個對映 m
n := s 的大小
x := 0
從初始化 j := 0、i := 0 開始，當 j < n 時，更新（將 j 增加 1），執行以下操作：
(將 m[s[j]] 增加 1)
如果 m[s[j]] 等於 1，則：
(將 x 增加 1)
當 (x > k 且 i <= j) 時，執行以下操作：
(將 m[s[i]] 減小 1)
如果 m[s[i]] 等於 0，則：
(將 x 減小 1)
(將 i 增加 1)
ans := ans 和 (j - i + 1) 的最大值
返回 ans
示例
讓我們看看以下實現以更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstringKDistinct(string s, int k) {
int ans = 0;
unordered_map<char, int> m;
int n = s.size();
int x = 0;
for (int j = 0, i = 0; j < n; j++) {
m[s[j]]++;
if (m[s[j]] == 1)
x++;
while (x > k && i <= j) {
m[s[i]]--;
if (m[s[i]] == 0)
x--;
i++;
}
ans = max(ans, j - i + 1);
}
return ans;
}
};
main() {
Solution ob;
cout << (ob.lengthOfLongestSubstringKDistinct("eceba", 2));
}輸入
"eceba", 2
輸出
3
更新於: 2020-07-21
1K+ 次檢視
廣告