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

2021年4月23日17:23:15 发表评论 729 次浏览

本文概述

给定一个字符串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但不等于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 ] * 26
  
     ans = []
     for i in range (n):
         fr[ ord (s[i]) - ord ( 'a' )] + = 1
  
     for 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 = 0
              
             for i in range (n):
                 if (s[i] = = ch1 and no <= k):
                     ans[i] = '2'
                     no + = 1
                      
                 if (fr展开 - 'a' ] = = k and 
                               flag = = 0 and 
                             ans[i] = = '1' ):
                     ans[i] = '2'
                     flag = 1
  
         print ("".join(ans))
     else :
          
         # If all cases fail
         print ( "NO" )
  
# Driver Code
if __name__ = = '__main__' :
  
     S = "abbbccc"
     N = len (S)
     K = 1
  
     DivideString(S, N, K)
  
# This code is contributed by mohit kumar 29

C#

//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

输出如下：

1111211

时间复杂度：O(N)

辅助空间：O(N)

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: