資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究字元頻率最多隻有一個為奇數的子字串數量
子字串是字串中連續字元的子集或序列。
現在，在這個問題中，我們需要找到字元頻率最多隻有一個為奇數的子字串的數量。讓我們看看我們應該如何解決這個問題。
讓我們透過一些例子來理解這個問題。
輸入
s = “ksjssjkk”
輸出
21
解釋 − 給定字串中字元的頻率如下所示：
k → 3
s → 3
j → 2
現在，最多隻有一個字元出現奇數次的子字串可以是：
取每個字元：'k'，'s'，'j'，'s'，'s'，'j'，'k'，'k' = 8
取兩個字母：'ss'，'kk' = 2
取三個字母：'sjs'，'jss'，'ssj'，'jkk' = 4
取四個字母：'jssj' = 1
取五個字母：'sjssj'，'jssjk'，'ssjkk' = 3
取六個字母：'jssjkk' = 1
取七個字母：'ksjssjk'，'sjssjkk' = 2
取八個字母：無字串
現在，將子字串的數量相加，我們得到 (8 + 2 + 4 + 1 + 3 + 1 + 2) = 21
輸入
s = “ab”
輸出
2
解釋 − 我們將得到 2 個子字串：'a'，'b'
問題說明
讓我們嘗試理解問題並找到解決方案。我們必須在字串中找到那些最多隻有一個字母出現奇數次的子字串，即在整體上，最多隻有一個字母的頻率為奇數。
解決方案 1：暴力解法
方法
這是一種易於理解的方法。我們將簡單地執行迴圈以訪問所有子字串，並且我們將繼續檢查是否只有一個字母具有奇數頻率。如果是，我們將子字串包含在最終輸出中。
示例
以下是各種程式語言中上述方法的實現：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
bool checkValid(const char* s){
int n = strlen(s);
// Define Frequency vector
int Freq[26] = {0};
// Define a variable named oddFreq to calculate total odd frequencies
int oddFreq = 0;
// Run a loop to count the frequencies of each character
for (int i = 0; i < n; i++) {
if (s[i] >= 'a' && s[i] <= 'z') {
Freq[s[i] - 'a']++;
}
}
// Run a loop to calculate the number of frequencies that are odd
for (int i = 0; i < 26; i++) {
if (Freq[i] % 2 != 0)
oddFreq++;
}
// Check if the frequency of any character is odd in number more than one then return false, else return true
if (oddFreq <= 1) return true;
else return false;
}
// Function to count the number of substrings with the frequency of at most one character as Odd
int Helper(const char* s){
// Define the size of the string
int n = strlen(s);
// Define a variable output initiated by zero
int output = 0;
// Run a loop to traverse through the string
for(int i = 0; i < n; i++) {
// Run another loop inside the first loop to get substrings
for (int j = i; j < n; j++) {
// Get substring from i to j
char S[100]; // Use an array to store the substring
strncpy(S, s + i, j - i + 1);
S[j - i + 1] = '\0'; // Null-terminate the substring
if (checkValid(S)) output++;
}
}
// Return the final output
return output;
}
int main(){
const char* s = "ksjssjkk";
// Call the helper function to get the final output
int output = Helper(s);
// Print the output
printf("The number of substrings with the frequency of at most one character as Odd is: %d", output);
return 0;
}
輸出
The number of substrings with the frequency of at most one character as Odd is: 21
#include <bits/stdc++.h>
using namespace std;
// Function which will check the string is valid
bool checkValid(string s){
int n = s.size();
// Define Frequency vector
int Freq[26] = {0};
// Define a variable named oddFreq to calculate total odd frequencies
int oddFreq = 0;
// Run a loop to count the frequencies of each character
for (int i = 0; i < n; i++) {
Freq[s[i] - 'a']++;
}
// Run a loop to calculate the number of frequencies that are odd
for (int i = 0; i < 26; i++) {
if (Freq[i] % 2 != 0)
oddFreq++;
}
// Check if the frequency of any character is odd in number more than one then return false, else return true
if (oddFreq <= 1) return true;
else return false;
}
// Function to count the number of substrings with the frequency of at most one character as Odd
int Helper(string s){
// Define the size of the string
int n = s.size();
// Define a variable output initiated by zero
int output = 0;
// Run a loop to traverse through the string
for(int i = 0; i < n; i++) {
// Run another loop inside the first loop to get substrings
for (int j = i; j < n; j++) {
// Get substring from i to j
string S = s.substr(i, j - i + 1);
if (checkValid(S)) output++;
}
}
// Return the final output
return output;
}
int main(){
// Give input string by the user
string s = "ksjssjkk" ;
// Call the helper function to get the final output
int output = Helper(s);
// Print the output
cout << "The number of substrings with the frequency of at most one character as Odd is: " << output;
return 0;
}
輸出
The number of substrings with the frequency of at most one character as Odd is: 21
public class Main {
public static boolean checkValid(String s) {
int n = s.length();
// Define Frequency vector
int[] Freq = new int[26];
// Define a variable named oddFreq to calculate total odd frequencies
int oddFreq = 0;
// Run a loop to count the frequencies of each character
for (int i = 0; i < n; i++) {
Freq[s.charAt(i) - 'a']++;
}
// Run a loop to calculate the number of frequencies that are odd
for (int i = 0; i < 26; i++) {
if (Freq[i] % 2 != 0)
oddFreq++;
}
// Check if the frequency of any character is odd in number more than one then return false, else return true
return oddFreq <= 1;
}
// Function to count the number of substrings with the frequency of at most one character as Odd
public static int Helper(String s) {
// Define the size of the string
int n = s.length();
// Define a variable output initiated by zero
int output = 0;
// Run a loop to traverse through the string
for (int i = 0; i < n; i++) {
// Run another loop inside the first loop to get substrings
for (int j = i; j < n; j++) {
// Get substring from i to j
String S = s.substring(i, j + 1); // Corrected to use substring
if (checkValid(S)) output++;
}
}
return output;
}
public static void main(String[] args) {
// Give input string by the user
String s = "ksjssjkk";
// Call the helper function to get the final output
int output = Helper(s);
// Print the output
System.out.println("The number of substrings with the frequency of at most one character as Odd is: " + output);
}
}
輸出
The number of substrings with the frequency of at most one character as Odd is: 21
# Function to check if the string is valid
def checkValid(s):
n = len(s)
# Define a frequency vector
Freq = [0] * 26
# Define a variable named oddFreq to calculate total odd frequencies
oddFreq = 0
# Run a loop to count the frequencies of each character
for i in range(n):
Freq[ord(s[i]) - ord('a')] += 1
# Run a loop to calculate the number of frequencies that are odd
for i in range(26):
if Freq[i] % 2 != 0:
oddFreq += 1
# Check if the frequency of any character is odd in number more than one then return False, else return True
return oddFreq <= 1
# Function to count the number of substrings with the frequency of at most one character as Odd
def Helper(s):
n = len(s)
# Define a variable output initiated by zero
output = 0
# Run a loop to traverse through the string
for i in range(n):
# Run another loop inside the first loop to get substrings
for j in range(i, n):
# Get substring from i to j
S = s[i:j+1]
if checkValid(S):
output += 1
# Return the final output
return output
def main():
# Give input string
s = "ksjssjkk"
# Call the Helper function to get the final output
output = Helper(s)
# Print the output
print("The number of substrings with the frequency of at most one character as Odd is:", output)
if __name__ == "__main__":
main()
輸出
The number of substrings with the frequency of at most one character as Odd is: 21
上述程式碼的複雜度
時間複雜度 − O(n^3); 其中 n 是字串的大小，這裡 (n^3) 是輔助函式的時間複雜度，而 checkValid 函式本身需要 (O(n)) 時間才能執行。
空間複雜度 − O(1); 我們在上述程式碼中沒有將任何變數儲存在某些資料結構中。
解決方案 2：使用位掩碼的最佳化解決方案
位掩碼
位掩碼是對值應用掩碼以保留、更改或修改給定資訊的片段的行為。掩碼確定要獲取哪些位以及要清除二進位制數中的哪些位。它可用於掩蓋值以使用各種按位運算來表示集合的子集。
方法
我們使用位掩碼來指示哪些字元被使用奇數次，並使用雜湊對映來跟蹤之前見過的位掩碼。在每次迭代後，我們將 hashmap[bitmask] 增加 1，表示我們熟悉此位掩碼。當 output += m[mask] 時，將計算使用偶數個字母的子字串。而 output+= m[mask^ (1<<j)] 將在恰好一個字母出現奇數次時計算子字串。
示例
以下是各種程式語言中上述方法的實現：
#include <bits/stdc++.h>
using namespace std;
int Helper(string s){
// Declare an Unordered map which would tell us if the frequency of bitmasks is odd or even that is 0 if that character has occurred even times and 1 if it has occurred odd times
unordered_map<int, int> m;
// Initiate the frequency bitmask
m[0] = 1;
// Store the current bitmask
int mask = 0;
// Initialize the output as 0
int output = 0;
// Run a loop to start masking
for (int i = 0; i < s.size(); ++i) {
// masking the current character
mask ^= (1 << (s[i] - 'a'));
// Count the substrings that have all alphabets used even the number of times
output += m[mask];
for (int j = 0; j < 26; ++j) {
// Count the substrings that have exactly 1 used character
output += m[mask ^ (1 << j)];
}
m[mask]++;
}
// Return the final output
return output;
}
int main(){
// Give input string by the user
string s = "ksjssjkk" ;
// Call the helper function to get the final output
int output = Helper(s);
// Print the output
cout << "The number of substrings with the frequency of at most one character as Odd is: " << output;
return 0;
}
輸出
The number of substrings with the frequency of at most one character as Odd is: 21
import java.util.HashMap;
public class Main {
public static int Helper(String s) {
HashMap<Integer, Integer> m = new HashMap<>();
// Initiate the frequency bitmask
m.put(0, 1);
// Store the current bitmask
int mask = 0;
int output = 0;
// Run a loop to start masking
for (int i = 0; i < s.length(); i++) {
// masking the current character
mask ^= (1 << (s.charAt(i) - 'a'));
// Count the substrings that have all alphabets used even the number of times
output += m.getOrDefault(mask, 0);
for (int j = 0; j < 26; j++) {
// Count the substrings that have exactly 1 used character
output += m.getOrDefault(mask ^ (1 << j), 0);
}
m.put(mask, m.getOrDefault(mask, 0) + 1);
}
// Return the final output
return output;
}
public static void main(String[] args) {
// Give input string by the user
String s = "ksjssjkk";
// Call the helper function to get the final output
int output = Helper(s);
System.out.println("The number of substrings with the frequency of at most one character as Odd is: " + output);
}
}
輸出
The number of substrings with the frequency of at most one character as Odd is: 21
def Helper(s):
# Initiate the frequency bitmask
m = {0: 1}
# Store the current bitmask
mask = 0
output = 0
# Run a loop to start masking
for i in range(len(s)):
# masking the current character
mask ^= (1 << (ord(s[i]) - ord('a')))
# Count the substrings that have all alphabets used even the number of times
output += m.get(mask, 0)
for j in range(26):
# Count the substrings that have exactly 1 used character
output += m.get(mask ^ (1 << j), 0)
m[mask] = m.get(mask, 0) + 1
# Return the final output
return output
def main():
# Give input string by the user
s = "ksjssjkk"
# Call the helper function to get the final output
output = Helper(s)
print("The number of substrings with the frequency of at most one character as Odd is:",output)
if __name__ == "__main__":
main()
輸出
The number of substrings with the frequency of at most one character as Odd is: 21
上述程式碼的複雜度
時間複雜度 − O(n*26); 其中 n 是字串的大小。因為對於字串的每個字元，我們都要檢查 26 個總字元。
空間複雜度 − O(1); 我們只使用了 map 資料結構，它將佔用 O(26) 空間，這與 O(1) 空間複雜度相對相等。
結論
在本文中，要查詢字元頻率最多隻有一個為奇數的子字串的數量。首先，我們將應用樸素方法使用迴圈獲取輸出，這是一種易於理解的方法，但這種方法的唯一缺點是它將以巨大的時間複雜度執行。但是，我們可以透過使用另一種稱為位掩碼的技術（使用雜湊對映）輕鬆推匯出程式碼的時間複雜度。特別是這個問題是位掩碼技術應用的一個特殊例子，因為它將時間複雜度從 O(n^3) 降低到 O(n)。在本文中，我們學習了位掩碼的使用和概念。
更新於：2024 年 2 月 5 日
299 次瀏覽
廣告