資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中最多包含兩個不同字元的最長子串
假設我們有一個字串s；我們必須找到最長子串t的長度，該子串最多包含2個不同的字元。
因此，如果輸入類似於“eceba”，則輸出將為3，因為t是“ece”，其長度為3。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式lengthOfLongestSubstringKDistinct()，它將接收s和k作為引數，
ans := 0
定義一個map 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
從主方法執行以下操作
返回lengthOfLongestSubstringKDistinct(s, 2)
示例
讓我們看看下面的實現，以便更好地理解：
#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;
}
int lengthOfLongestSubstringTwoDistinct(string s){
return lengthOfLongestSubstringKDistinct(s, 2);
}
};
main(){
Solution ob;
cout << (ob.lengthOfLongestSubstringTwoDistinct("eceba"));
}輸入
"eceba"
輸出
3
更新於：2020年11月18日
1K+ 次瀏覽
廣告