資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學由字元拼接形成的字串的最大長度，要求每個字元的出現頻率為偶數。
連線運算子用於連線一個或多個字串，以生成一個新的字串，該字串是用於透過連線生成它的字串的組合。在下面的文章中，我們將只在輸入字串中使用大寫字母。
連線運算子用於連線一個或多個字串，以生成一個新的字串，該字串是用於透過連線生成它的字串的組合。在下面的文章中，我們將只在輸入字串中使用大寫字母。
讓我們透過一些例子來理解這個問題。
輸入
"FEFEE", "EFF", "HGG", "AD", "HHH"
說明 − 在這個例子中，我們可以看到，透過連線形成的字串的最大長度，其每個字元的出現頻率為偶數的是“FEFEEEFFHGGHHH”，得到的字串長度為14。因此，‘14’是最終輸出。
F的頻率− 4
E的頻率− 4
H的頻率− 4
G的頻率− 2
輸入
"ABCD", "AVP", "ADDDC", "BCCCA", "HH", "CA"
輸出
18
說明 − 在這個例子中，我們可以看到，透過連線形成的字串的最大長度，其每個字元的出現頻率為偶數的是“ABCDADDDCBCCCAHHCA”，得到的字串長度為18。因此，‘18’是最終輸出。
A的頻率：4
B的頻率：2
C的頻率：6
D的頻率：4
H的頻率：2
問題說明
讓我們嘗試理解這個問題並找到它的解決方案。在下面的文章中，我們將討論一種方法，用於查詢由給定字串陣列中的字串連線形成的字串的最大長度，要求每個字元的出現頻率為偶數。該解決方案將涉及遞迴和回溯。對於陣列中的每個字串，我們將有兩個選擇——將其包含到我們最終的字串中（要求每個字元的出現頻率為偶數），或者不包含該字串。
因此，這種方法涉及建立一個遞迴函式，併為每個字串遞迴呼叫兩次——一次包含它，另一次不包含它。包含每個字串後，繼續檢查最終字串中的所有字元是否具有偶數頻率，並繼續更新由連線形成的、每個字元具有偶數頻率的字串的最大長度。
遞迴演算法
建立一個遞迴函式，其基本情況是當索引等於陣列的大小時，函式將返回。現在，在這個函式中，我們將考慮兩種情況，在第一種情況下，我們將不包含當前字串並進行遞迴呼叫。
而在第二種情況下，我們將包含它，然後使用另一個函式（CheckValid）檢查當前輸出字串是否滿足要求，即它是否具有每個字元的偶數頻率。
如果滿足條件，我們將儲存該字串的長度（如果它大於之前的長度）。
接下來，我們將進行另一個遞迴呼叫，在這個呼叫中我們將包含當前字串。
這樣，我們將得到最終的輸出大小。
示例
以下是上述方法在各種程式語言中的實現：
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
// Function to check whether the string has an even frequency of each character or not
bool CheckValid(const char *str){
// Declare a frequency array that would work like a map to store the count of each alphabet
int mapArray[26] = { 0 };
// Store the frequency of each alphabet, we will take uppercase English alphabets only in our string
for (int i = 0; i < strlen(str); i++) {
mapArray[str[i] - 'A']++;
}
// Check if the frequency of any alphabet is odd, if yes return false
for (int i = 0; i < 26; i++) {
if (mapArray[i] % 2 == 1) {
return false;
}
}
// If we have all our alphabets in even count, we can return true
return true;
}
// Function to find the maximum length of a string having an even frequency of each character formed by concatenation
void FindMaxLength(const char *array[], int i, int size, const char *s, int* maxi){
// Check if we have taken all strings from our array that is check the base case
if (i == size) {
return;
}
// Do not Include the string
FindMaxLength(array, i + 1, size, s, maxi);
// Include the string
char combined[100]; // Choose a reasonable maximum length for your combined string
strcpy(combined, s);
strcat(combined, array[i]);
if (CheckValid(combined)) {
int currentLength = strlen(combined);
if (currentLength > *maxi) {
*maxi = currentLength;
}
}
FindMaxLength(array, i + 1, size, combined, maxi);
}
int main(){
// Size of the string provided by the user
int size = 5;
// String provided by the user
const char* array[5] = { "FEFEE", "EFF", "HGG", "AD", "HHH" };
// Declare a variable to store the maximum length of string formed by concatenation having even frequency of each character
int maxi = 0;
// Call the function to find the maximum length of string formed by concatenation having an even frequency of each character
FindMaxLength(array, 0, size, "", &maxi);
// Print the final output
printf("The maximum length of string formed by concatenation having an even frequency of each character is: %d", maxi);
return 0;
}
輸出
The maximum length of string formed by concatenation having an even frequency of each character is: 14
#include <bits/stdc++.h>
using namespace std;
// Function to check whether the string has an even frequency of each character or not
bool CheckValid(string str){
// Declare a frequency array that would work like a map to store the count of each alphabet
int mapArray[26] = { 0 };
// Store the frequency of each alphabet, we will take uppercase English alphabets only in our string
for (int i = 0; i < str.length(); i++) {
mapArray[str[i] - 'A']++;
}
// Check if the frequency of any alphabet is odd, if yes return false
for (int i = 0; i < 26; i++) {
if (mapArray[i] % 2 == 1) {
return false;
}
}
// If we have all our alphabets in even count, we can return true
return true;
}
// Function to find the maximum length of a string having an even frequency of each character formed by concatenation
void FindMaxLength(string array[], int i, int size, string s, int& maxi){
// Check if we have taken all strings from our array that is check the base case
if (i == size) {
return;
}
// Do not Include the string
FindMaxLength(array, i + 1, size, s, maxi);
// Include the string
s += array[i];
// Check if the string collected is giving us a string with all character counts as even, constituted in it
if(CheckValid(s)) {
// Store the maximum of the previous and current length
if(s.length() > maxi) {
maxi = s.length();
}
}
FindMaxLength(array, i + 1, size, s, maxi);
}
int main(){
// Size of the string provided by the user
int size = 5;
// String provided by the user
string array[5] = { "FEFEE", "EFF", "HGG", "AD", "HHH" };
// Declare a variable to store the maximum length of string formed by concatenation having even frequency of each character
int maxi = 0;
// Call the function to find the maximum length of string formed by concatenation having an even frequency of each character
FindMaxLength(array, 0, size, "", maxi);
// Print the final output
cout << "The maximum length of string formed by concatenation having an even frequency of each character is: "<< maxi <<endl;
return 0;
}
輸出
The maximum length of string formed by concatenation having an even frequency of each character is: 14
public class Main {
public static boolean CheckValid(String str) {
// Declare a frequency array that would work like a map to store the count of each alphabet
int[] mapArray = new int[26];
// Store the frequency of each alphabet, we will take uppercase English alphabets only in our string
for (int i = 0; i < str.length(); i++) {
mapArray[str.charAt(i) - 'A']++;
}
// Check if the frequency of any alphabet is odd, if yes return false
for (int i = 0; i < 26; i++) {
if (mapArray[i] % 2 == 1) {
return false;
}
}
// If we have all our alphabets in even count, we can return true
return true;
}
//Function to find the maximum length of a string having an even frequency of each character formed by concatenation
public static void FindMaxLength(String[] array, int i, int size, String s, int[] maxi) {
// Check if we have taken all strings from our array that is check the base case
if (i == size) {
return;
}
FindMaxLength(array, i + 1, size, s, maxi);
s += array[i];
if (CheckValid(s)) {
int currentLength = s.length();
// Store the maximum of the previous and current length
if (currentLength > maxi[0]) {
maxi[0] = currentLength;
}
}
FindMaxLength(array, i + 1, size, s, maxi);
}
public static void main(String[] args) {
int size = 5;
String[] array = { "FEFEE", "EFF", "HGG", "AD", "HHH" };
int[] maxi = { 0 };
FindMaxLength(array, 0, size, "", maxi);
System.out.println("The maximum length of a string formed by concatenation having an even frequency of each character is: " + maxi[0]);
}
}
輸出
The maximum length of a string formed by concatenation having an even frequency of each character is: 14
# Function to check whether the string has an even frequency of each character or not
def CheckValid(s):
# Declare a frequency array that would work like a map to store the count of each alphabet
mapArray = [0] * 26
# Store the frequency of each alphabet; we will take uppercase English alphabets only in our string
for char in s:
if 'A' <= char <= 'Z':
mapArray[ord(char) - ord('A')] += 1
# Check if the frequency of any alphabet is odd; if yes, return False
for count in mapArray:
if count % 2 == 1:
return False
# If we have all our alphabets in even count, we can return True
return True
# Function to find the maximum length of a string having an even frequency of each character formed by concatenation
def FindMaxLength(array, i, size, s, maxi):
# Check if we have taken all strings from our array, that is, check the base case
if i == size:
return
# Do not include the string
FindMaxLength(array, i + 1, size, s, maxi)
# Include the string
s += array[i]
# Check if the string collected is giving us a string with all character counts as even, constituted in it
if CheckValid(s):
# Store the maximum of the previous and current length
if len(s) > maxi[0]:
maxi[0] = len(s)
FindMaxLength(array, i + 1, size, s, maxi)
if __name__ == "__main__":
size = 5
# String provided by the user
array = ["FEFEE", "EFF", "HGG", "AD", "HHH"]
# Declare a variable to store the maximum length of string formed by concatenation having even frequency of each character
maxi = [0]
# Call the function to find the maximum length of string formed by concatenation having an even frequency of each character
FindMaxLength(array, 0, size, "", maxi)
# Print the final output
print("The maximum length of a string formed by concatenation having an even frequency of each character is:", maxi[0])
輸出
The maximum length of a string formed by concatenation having an even frequency of each character is: 14
上述程式碼的複雜度
時間複雜度 − O(n * m * (2^n))；其中‘n’是陣列的長度，即給定字串的總數，‘m’是陣列中出現的最長字串的長度。每個字串將在遞迴呼叫中執行兩次，使得遞迴函式的時間複雜度為‘2^n’，而CheckValid函式將花費與由連線形成的最長字串的大小成正比的時間，這可能高達(n * m)，即當我們將給定陣列中包含的每個字串都包含在最終答案中的情況。
空間複雜度 − O(1)；我們在上面的程式碼中沒有在任何資料結構中儲存任何變數。
結論
在本文中，我們找到了一種方法來查詢由連線形成的字串的最大長度，要求每個字元的出現頻率為偶數。我們使用遞迴和回溯等概念理解了這種方法。但是，上面給出的程式碼的時間複雜度非常大，因此該程式碼只能在字串和陣列的大小有限制的情況下工作。
更新於： 2024年2月5日
74 次瀏覽
廣告