检查一个字符串是否可以分为两个相同的K频率字符字符串

本文概述

C ++
Java
Python3
C#

给定一个字符串S和一个整数K，任务是检查是否有可能将这些字符分配到两个字符串中，使两个字符串中频率为K的字符的计数相等。
如果可能，则输出一个由1和2组成的序列，这表示哪个字符应该放在哪个字符串中。
否则, 打印NO
注意：这些新字符串之一可以为空。
例子：

输入：S ="abbbccc", K = 1
输出：1111211
说明：两个字符串是"abbbcc"和"c"。因此, 两个字符串都恰好具有频率为K(= 1)的1个字符。
输入：S ="aaaa", K = 3
输出：1111
说明：字符串可分为"aaaa"和""。因此, 两个字符串中没有字符具有频率3。

方法：
请按照以下步骤解决问题：
【检查一个字符串是否可以分为两个相同的K频率字符字符串】如果初始字符串中频率为K的字符总数是偶数，那么这些字符可以相等地放在两个字符串中，而其余的字符(频率不等于K)可以放在这两组中的任何一组中。
如果初始字符串中频率为K的字符总数是奇数，那么如果初始字符串中有一个字符的频率大于K但不等于2K，那么这样的分布是可能的。

描述：
S ="abceeee", K = 1
分为"abeee"和"ce"。因此, 两个字符串都具有2个频率为1的字符。

如果初始字符串中频率为K的字符总数是奇数，那么如果初始字符串中有一个频率为2K的字符，那么这种分布是可能的。

描述：
S ="aaaabbccdde", K = 2
分为"aabbc"和"aaddce", 以便两个字符串都具有两个频率为2的字符。

如果上述三个条件均失败, 则答案为"NO"
下面是上述方法的实现：
C ++

//C++ implementation of the //above approach #include < bits/stdc++.h> using namespace std; //Function to print the //arrangement of characters void DivideString(string s, int n, int k) { int i, c = 0, no = 1; int c1 = 0, c2 = 0; //Stores frequency of //characters int fr[26] = { 0 }; string ans = "" ; for (i = 0; i < n; i++) { fr展开 - 'a' ]++; }char ch, ch1; for (i = 0; i < 26; i++) {//Count the character //having frequency K if (fr[i] == k) { c++; }//Count the character //having frequency //greater than K and //not equal to 2K if (fr[i]> k & & fr[i] != 2 * k) { c1++; ch = i + 'a' ; }if (fr[i] == 2 * k) { c2++; ch1 = i + 'a' ; } }for (i = 0; i < n; i++) ans = ans + "1" ; map< char , int> mp; if (c % 2 == 0 || c1> 0 || c2> 0) { for (i = 0; i < n; i++) {//Case 1 if (fr展开 - 'a' ] == k) { if (mp.find(s[i]) != mp.end()) { ans[i] = '2' ; } else { if (no < = (c /2)) { ans[i] = '2' ; no++; mp展开] = 1; } } } }//Case 2 if (c % 2 == 1 & & c1> 0) { no = 1; for (i = 0; i < n; i++) { if (s[i] == ch & & no < = k) {ans[i] = '2' ; no++; } } }//Case 3 if (c % 2 == 1 & & c1 == 0) { no = 1; int flag = 0; for ( int i = 0; i < n; i++) { if (s[i] == ch1 & & no < = k) { ans[i] = '2' ; no++; } if (fr展开 - 'a' ] == k & & flag == 0 & & ans[i] == '1' ) { ans[i] = '2' ; flag = 1; } } }cout < < ans < < endl; } else { //If all cases fail cout < < "NO" < < endl; } }//Driver Code int main() {string S = "abbbccc" ; int N = S.size(); int K = 1; DivideString(S, N, K); return 0; }

Java

//Java program for the above problem import java.util.*; class GFG{//Function to print the //arrangement of characters public static void DivideString(String s, int n, int k) { int i, c = 0 , no = 1 ; int c1 = 0 , c2 = 0 ; //Stores frequency of //characters int [] fr = new int [ 26 ]; char [] ans = new char [n]; for (i = 0 ; i < n; i++) { fr展开++; } char ch = 'a' , ch1 = 'a' ; for (i = 0 ; i < 26 ; i++) { //Count the character //having frequency K if (fr[i] == k) { c++; } //Count the character //having frequency //greater than K and //not equal to 2K if (fr[i]> k & & fr[i] != 2 * k) { c1++; ch = ( char )(i + 'a' ); } if (fr[i] == 2 * k) { c2++; ch1 = ( char )(i + 'a' ); } } for (i = 0 ; i < n; i++) ans[i] = '1' ; HashMap< Character, Integer> mp = new HashMap< > (); if (c % 2 == 0 || c1> 0 || c2> 0 ) { for (i = 0 ; i < n; i++) { //Case 1 if (fr展开 == k) { if (mp.containsKey(s.charAt(i))) { ans[i] = '2' ; } else { if (no < = (c /2 )) { ans[i] = '2' ; no++; mp.replace(s.charAt(i), 1 ); } } } } //Case 2 if ( (c % 2 == 1 ) & & (c1> 0 ) ) { no = 1 ; for (i = 0 ; i < n; i++) { if (s.charAt(i) == ch & & no < = k) { ans[i] = '2' ; no++; } } } //Case 3 if (c % 2 == 1 & & c1 == 0 ) { no = 1 ; int flag = 0 ; for (i = 0 ; i < n; i++) { if (s.charAt(i) == ch1 & & no < = k) { ans[i] = '2' ; no++; } if (fr展开 == k & & flag == 0 & & ans[i] == '1' ) { ans[i] = '2' ; flag = 1 ; } } } System.out.println(ans); } else {//If all cases fail System.out.println( "NO" ); } } //Driver code public static void main(String[] args) { String S = "abbbccc" ; int N = S.length(); int K = 1 ; DivideString(S, N, K); } }//This code is contributed by divyeshrabadiya07

Python3

# Python3 implementation of the # above approach# Function to print the # arrangement of characters def DivideString(s, n, k):c = 0 no = 1 c1 = 0 c2 = 0# Stores frequency of # characters fr = [ 0 ] * 26ans = [] for i in range (n): fr[ ord (s[i]) - ord ( 'a' )] + = 1for i in range ( 26 ):# Count the character # having frequency K if (fr[i] = = k): c + = 1# Count the character having # frequency greater than K and # not equal to 2K if (fr[i]> k and fr[i] ! = 2 * k): c1 + = 1 ch = chr ( ord ( 'a' ) + i)if (fr[i] = = 2 * k): c2 + = 1 ch1 = chr ( ord ( 'a' ) + i)for i in range (n): ans.append( "1" )mp = {} if (c % 2 = = 0 or c1> 0 or c2> 0 ): for i in range (n):# Case 1 if (fr[ ord (s[i]) - ord ( 'a' )] = = k): if (s[i] in mp): ans[i] = '2'else : if (no < = (c //2 )): ans[i] = '2' no + = 1 mp展开] = 1# Case 2 if (c % 2 = = 1 and c1> 0 ): no = 1 for i in range (n): if (s[i] = = ch and no < = k): ans[i] = '2' no + = 1# Case 3 if (c % 2 = = 1 and c1 = = 0 ): no = 1 flag = 0for i in range (n): if (s[i] = = ch1 and no < = k): ans[i] = '2' no + = 1if (fr展开 - 'a' ] = = k and flag = = 0 and ans[i] = = '1' ): ans[i] = '2' flag = 1print ("".join(ans)) else :# If all cases fail print ( "NO" )# Driver Code if __name__ = = '__main__' :S = "abbbccc" N = len (S) K = 1DivideString(S, N, K)# This code is contributed by mohit kumar 29

//C# program for the above problem using System; using System.Collections.Generic; class GFG{ //Function to print the //arrangement of characters public static void DivideString( string s, int n, int k) { int i, c = 0, no = 1; int c1 = 0, c2 = 0; //Stores frequency of //characters int [] fr = new int [26]; char [] ans = new char [n]; for (i = 0; i < n; i++) { fr展开 - 'a' ]++; } char ch = 'a' , ch1 = 'a' ; for (i = 0; i < 26; i++) { //Count the character //having frequency K if (fr[i] == k) { c++; } //Count the character having //frequency greater than K and //not equal to 2K if (fr[i]> k & & fr[i] != 2 * k) { c1++; ch = ( char )(i + 'a' ); } if (fr[i] == 2 * k) { c2++; ch1 = ( char )(i + 'a' ); } } for (i = 0; i < n; i++) ans[i] = '1' ; Dictionary< char , int> mp = new Dictionary< char , int> (); if (c % 2 == 0 || c1> 0 || c2> 0) { for (i = 0; i < n; i++) { //Case 1 if (fr展开 - 'a' ] == k) { if (mp.ContainsKey(s[i])) { ans[i] = '2' ; } else { if (no < = (c /2)) { ans[i] = '2' ; no++; mp展开] = 1; } } } } //Case 2 if ( (c % 2 == 1) & & (c1> 0) ) { no = 1; for (i = 0; i < n; i++) { if (s[i]== ch & & no < = k) { ans[i] = '2' ; no++; } } } //Case 3 if (c % 2 == 1 & & c1 == 0) { no = 1; int flag = 0; for (i = 0; i < n; i++) { if (s[i] == ch1 & & no < = k) { ans[i] = '2' ; no++; } if (fr展开 - 'a' ] == k & & flag == 0 & & ans[i] == '1' ) { ans[i] = '2' ; flag = 1; } } } Console.Write(ans); } else { //If all cases fail Console.Write( "NO" ); } } //Driver code public static void Main( string [] args) { string S = "abbbccc" ; int N = S.Length; int K = 1; DivideString(S, N, K); } } //This code is contributed by rutvik_56

输出如下：