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

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

本文概述

S ="abceeee", K = 1

S ="aaaabbccdde", K = 2

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