Given a string S and an integer K, the task is to check if it is possible to distribute these characters into two strings such that the count of characters having a frequency K in both strings is equal.
If it is possible, then print a sequence consisting of 1 and 2, which denotes which character should be placed in which string. Otherwise, print NO.
Note: One of these new strings can be empty.
Examples:
Input: S = “abbbccc”, K = 1
Output: 1111211
Explanation:
The two strings are “abbbcc” and “c”.
Hence, both the strings have exactly 1 character having frequency K( = 1).Input: S = “aaaa”, K = 3
Output: 1111
Explanation:
Strings can be split into “aaaa” and “”.
Hence, no character has frequency 3 in both the strings.
Approach:
Follow the steps below to solve the problem:
- Check for the following three conditions to determine if a split is possible or not:
1. If the total number of characters having a frequency K in the initial string is even, then these characters can be placed equally into two strings and the rest of the characters(having a frequency not equal to K) can be placed in any of the two groups.
2. If the total number of characters having a frequency K in the initial string is odd, then if there is a character in the initial string having a frequency greater than K but not equal to 2K, then such a distribution is possible.
Illustration:
S =”abceeee”, K = 1
Split into “abeee” and “ce”. Hence, both the strings have 2 characters with frequency 1.
3. If the total number of characters having a frequency K in the initial string is odd, then if there is a character in the initial string having a frequency equal to 2K, then such a distribution is possible.
Illustration:
S =”aaaabbccdde”, K = 2
Split into “aabbc” and “aaddce” so that both the strings have two characters with frequency 2.
- If all the three conditions mentioned above fail, then the answer is “NO”.
Below is the implementation of the above approach:
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[s[i] - '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[s[i] - 'a' ] == k) { if (mp.find(s[i]) != mp.end()) { ans[i] = '2' ; } else { if (no <= (c / 2)) { ans[i] = '2' ; no++; mp[s[i]] = 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[s[i] - '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[s.charAt(i) - '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' ; HashMap<Character, Integer> mp = new HashMap<>(); if (c % 2 == 0 || c1 > 0 || c2 > 0 ) { for (i = 0 ; i < n; i++) { // Case 1 if (fr[s.charAt(i) - 'a' ] == 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[s.charAt(i) - 'a' ] == 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[s[i]] = 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[s[i] - '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[s[i] - '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[s[i] - 'a' ] == k) { if (mp.ContainsKey(s[i])) { ans[i] = '2' ; } else { if (no <= (c / 2)) { ans[i] = '2' ; no++; mp[s[i]] = 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[s[i] - '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 |
Javascript
<script> // JavaScript program for the above problem // Function to print the // arrangement of characters function DivideString(s, n, k) { var i, c = 0, no = 1; var c1 = 0, c2 = 0; // Stores frequency of // characters var fr = new Array(26).fill(0); var ans = []; for (i = 0; i < n; i++) { fr[s[i].charCodeAt(0) - "a" .charCodeAt(0)]++; } var 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 = String.fromCharCode(i + "a" .charCodeAt(0)); } if (fr[i] === 2 * k) { c2++; ch1 = String.fromCharCode(i + "a" .charCodeAt(0)); } } for (i = 0; i < n; i++) ans.push( "1" ); var mp = {}; if (c % 2 === 0 || c1 > 0 || c2 > 0) { for (i = 0; i < n; i++) { // Case 1 if (fr[s[i].charCodeAt(0) - "a" .charCodeAt(0)] === k) { if (mp.hasOwnProperty(s[i])) { ans[i] = "2" ; } else { if (no <= parseInt(c / 2)) { ans[i] = "2" ; no++; mp[s[i]] = 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; var flag = 0; for (i = 0; i < n; i++) { if (s[i] === ch1 && no <= k) { ans[i] = "2" ; no++; } if ( fr[s[i].charCodeAt(0) - "a" .charCodeAt(0)] === k && flag === 0 && ans[i] === "1" ) { ans[i] = "2" ; flag = 1; } } } document.write(ans.join( "" )); } else { // If all cases fail document.write( "NO" ); } } // Driver code var S = "abbbccc" ; var N = S.length; var K = 1; DivideString(S, N, K); </script> |
1111211
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!