数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
广告