資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學至少包含前K個字母一次的子串計數
在這個問題中，我們需要計算包含至少一個所有K個字元的子串。
在這裡，我們將使用兩種不同的方法來解決這個問題。第一種方法獲取給定字串的所有子串，檢查子串是否包含所有K個字元，並計算包含所有K個字元的子串。
第二種方法使用滑動視窗技術來解決這個問題。
問題陳述 - 我們給定一個包含N個字元的字串alpha。此外，我們還給定K，表示包含多個僅前K個字母字元的字串。我們需要計算包含所有K個字元至少出現一次的子串總數。
示例
輸入
alpha = "abcdda", K = 4;
輸出
4
解釋 - 包含所有4個字元的子串是'abcd'，'abcdd'，'abcdda'和'bcdda'。
輸入
alpha = "abc", K = 5
輸出
0
解釋 - 給定字串中沒有包含所有5個字元的子串。
輸入
alpha = "ccbba"; K = 3;
輸出
2
解釋 - 字串'ccbba'和'cbba'包含所有3個字元。
方法1
在這種方法中，我們將遍歷字串以獲取所有子串並將它們儲存在列表中。之後，我們將計算列表中包含所有K個字元至少一次的字串的數量。
演算法
步驟1 - 初始化'subStr'列表以儲存所有子串。
步驟2 - 開始遍歷字串。此外，使用巢狀迴圈從1到字串大小 - p進行迭代。
步驟3 - 使用substr()方法從第p個索引獲取子串，長度等於q。並將子串推入'subStr'列表。
步驟4 - 將'result'初始化為0，以儲存有效子串的計數。
步驟5 - 開始遍歷子串列表，並定義'freq'對映以儲存當前字串中字元的頻率。還將'chars'初始化為0，以計算字串中不同的字元。
步驟6 - 開始遍歷當前字串。如果對映中字元的頻率為0，則更新頻率並將'chars'值加1。
步驟7 - 如果chars的值等於K，則將'result'加1。
步驟8 - 返回result值。
示例
#include <bits/stdc++.h>
using namespace std;
int numberOfSubstrings(string alpha, int K) {
// Finding all substrings of the alpha
vector<string> subStr;
for (int p = 0; p < alpha.size(); p++) {
for (int q = 1; q <= alpha.size() - p; q++) {
// Get substring from p to q
subStr.push_back(alpha.substr(p, q));
}
}
// Counting the number of substrings containing all K characters
int result = 0;
for (int p = 0; p < subStr.size(); p++) {
// To store the frequency of characters in the current substring
map<char, int> freq;
// To store the totally different characters
int chars = 0;
// Traverse substring
for (int q = 0; q < subStr[p].size(); q++) {
// If a character does not exist in the map, increment chars
if (freq[subStr[p][q]] == 0) {
freq[subStr[p][q]]++;
chars++;
}
}
// If different chars are the same as K, the string is valid.
if (chars == K) {
result++;
}
}
return result;
}
int main() {
string alpha = "abcdda";
int K = 4;
cout << "The number of substrings containing all K characters at least once is " << numberOfSubstrings(alpha, K);
return 0;
}
輸出
The number of substrings containing all K characters at least once is 4
時間複雜度 - O(N*N*M)，其中O(N*N)用於獲取所有子串，O(M)用於遍歷字串。
空間複雜度 - O(N*N)用於儲存所有子串。
方法2
在這種方法中，我們將使用滑動視窗技術來計算包含所有K個字元至少一次的子串的數量。
演算法
步驟1 - 初始化'freq'對映以儲存字元頻率，'left'和'right'指標為0，表示滑動視窗指標，'len'為字串長度，'cnt'為0，用於儲存字串計數。
步驟2 - 直到'right'小於字串長度，進行迭代。
步驟3 - 為對映中'right'索引處的字元增加字元頻率。
步驟4 - 如果對映的大小等於K，則表示我們得到了包含所有K個字元的子串。因此，請按照以下步驟操作。
步驟4.1 - 直到對映的大小等於K，進行迭代。
步驟4.2 - 將'len - right'新增到'cnt'。
步驟4.3 - 要從當前視窗中刪除左字元，請減少對映中其頻率。如果對映中字元的頻率為0，則從對映中刪除該字元。
步驟4.4 - 在巢狀迴圈中遞增'left'指標。
步驟4.5 - 在主迴圈中遞增'right'指標。
步驟5 - 否則，遞增'right'指標值。
步驟6 - 返回'cnt'值。
示例
讓我們透過示例輸入瞭解滑動視窗技術如何解決問題。
輸入 - 'abcdaabc'，K = 4
第一個視窗將是'abcd'，包含所有4個字元。因此，我們可以說(0, 3)，(0, 4)，(0, 5)，(0, 6)和(0, 7)所有子串都包含所有K個字元。
之後，從1到4的下一個視窗包含所有字元。因此，(1, 4)，(1,5)，(1, 6)和(1, 7)所有子串都至少包含一次所有K個字元。
透過這種方式，我們可以計算每個有效視窗的子串數量。
#include <bits/stdc++.h>
using namespace std;
int numberOfSubstrings(string alpha, int K) {
// For storing the frequency of characters
unordered_map<char, int> freq;
int left = 0, right = 0, len = alpha.size(), cnt = 0;
// Traveres the string
while (right < len) {
// Update character frequency
freq[alpha[right]]++;
// If the size of the map contains all K characters
if (freq.size() == K) {
// Traverse the map until the map size is k
while (freq.size() == K) {
// Add all valid substrings.
// If (left, right) contains all K characters, (left, right + 1), (left + right + 2), ... also contains.
cnt += len - right;
// Update character frequency
freq[alpha[left]]--;
// Remove the character if its frequency is 0.
if (freq[alpha[left]] == 0)
freq.erase(alpha[left]);
// Move to the next character from left
left++;
}
// Increment the right pointer.
right++;
}
// Increment right by 1
else {
right++;
}
}
// Return the value of cnt
return cnt;
}
int main() {
string alpha = "abcdda";
int K = 4;
cout << "The number of substrings containing all K characters at least once is " << numberOfSubstrings(alpha, K);
return 0;
}
輸出
The number of substrings containing all K characters at least once is 4
時間複雜度 - O(N)，用於滑動視窗。
空間複雜度 - O(K)，用於在對映中儲存頻率。
程式設計師也可以使用陣列來儲存字元的頻率而不是對映，因為我們可以比對映更快地訪問陣列中的元素。為了進行更多練習，程式設計師嘗試解決我們需要計算僅包含所有K個字元一次的字串數量的問題。
93 次瀏覽
