Reorder the given string to form a K-concatenated string
Given a string S and an integer K. The task is to form a string T such that the string T is a reordering of the string S in a way that it is a K-Concatenated-String. A string is said to be a K-Concatenated-String if it contains exactly K copies of some string.
For example, the string “geekgeek” is a 2-Concatenated-String formed by concatenating 2 copies of the string “geek”.
Note: Multiple answers are possible.
Examples:
Input : s = “gkeekgee”, k=2
Output: geekgeek
eegkeegk is another possible K-Concatenated-String
Input: s = “abcd”, k=2
Output: Not Possible
Approach: To find a valid ordering that is a K-Concatenated-string, iterate through the entire string and maintain a frequency array for the characters to hold the number of times each character occurs in a string. Since, in a K-Concatenated-string, the number of times a character occurs should be divisible by K. If any character is found not following this, then the string cant be ordered in any way to represent a K-Concatenated-string, else there can be exactly (Frequency of ith character / K) copies of the ith character in a single copy of the k-Concatenated-string. Such single copies when repeated K times form a valid K-Concatenated-string.
Below is the implementation of the above approach:
C++
// C++ program to form a // K-Concatenated-String from a given string #include <bits/stdc++.h> using namespace std; // Function to print the k-concatenated string string kStringGenerate(string str, int k) { // maintain a frequency table // for lowercase letters int frequency[26] = { 0 }; int len = str.length(); for ( int i = 0; i < len; i++) { // for each character increment its frequency // in the frequency array frequency[str[i] - 'a' ]++; } // stores a single copy of a string, // which on repeating forms a k-string string single_copy = "" ; // iterate over frequency array for ( int i = 0; i < 26; i++) { // if the character occurs in the string, // check if it is divisible by k, // if not divisible then k-string cant be formed if (frequency[i] != 0) { if ((frequency[i] % k) != 0) { string ans = "Not Possible" ; return ans; } else { // ith character occurs (frequency[i]/k) times in a // single copy of k-string int total_occurrences = (frequency[i] / k); for ( int j = 0; j < total_occurrences; j++) { single_copy += char (i + 97); } } } } string kString; // append the single copy formed k times for ( int i = 0; i < k; i++) { kString += single_copy; } return kString; } // Driver Code int main() { string str = "gkeekgee" ; int K = 2; string kString = kStringGenerate(str, K); cout << kString; return 0; } |
Java
// Java program to form a // K-Concatenated-String // from a given string import java.io.*; import java.util.*; import java.lang.*; class GFG { // Function to print // the k-concatenated string static String kStringGenerate(String str, int k) { // maintain a frequency table // for lowercase letters int frequency[] = new int [ 26 ]; Arrays.fill(frequency, 0 ); int len = str.length(); for ( int i = 0 ; i < len; i++) { // for each character // increment its frequency // in the frequency array frequency[str.charAt(i) - 'a' ]++; } // stores a single copy // of a string, which on // repeating forms a k-string String single_copy = "" ; // iterate over // frequency array for ( int i = 0 ; i < 26 ; i++) { // if the character occurs // in the string, check if // it is divisible by k, // if not divisible then // k-string cant be formed if (frequency[i] != 0 ) { if ((frequency[i] % k) != 0 ) { String ans = "Not Possible" ; return ans; } else { // ith character occurs // (frequency[i]/k) times in // a single copy of k-string int total_occurrences = (frequency[i] / k); for ( int j = 0 ; j < total_occurrences; j++) { single_copy += ( char )(i + 97 ); } } } } String kString = "" ; // append the single // copy formed k times for ( int i = 0 ; i < k; i++) { kString += single_copy; } return kString; } // Driver Code public static void main(String[] args) { String str = "gkeekgee" ; int K = 2 ; String kString = kStringGenerate(str, K); System.out.print(kString); } } |
Python3
# Python 3 program to form a # K-Concatenated-String from a given string # Function to print the k-concatenated string def kStringGenerate(st, k): # maintain a frequency table # for lowercase letters frequency = [ 0 ] * 26 length = len (st) for i in range (length): # for each character increment its frequency # in the frequency array frequency[ ord (st[i]) - ord ( 'a' )] + = 1 # stores a single copy of a string, # which on repeating forms a k-string single_copy = "" # iterate over frequency array for i in range ( 26 ): # if the character occurs in the string, # check if it is divisible by k, # if not divisible then k-string cant be formed if (frequency[i] ! = 0 ): if ((frequency[i] % k) ! = 0 ): ans = "Not Possible" return ans else : # ith character occurs (frequency[i]/k) times in a # single copy of k-string total_occurrences = (frequency[i] / / k) for j in range (total_occurrences): single_copy + = chr (i + 97 ) kString = "" # append the single copy formed k times for i in range (k): kString + = single_copy return kString # Driver Code if __name__ = = "__main__" : st = "gkeekgee" K = 2 kString = kStringGenerate(st, K) print (kString) # This code is contributed by ukasp. |
C#
// C# program to form a // K-Concatenated-String // from a given string using System; class GFG { // Function to print // the k-concatenated string static String kStringGenerate(String str, int k) { // maintain a frequency table // for lowercase letters int []frequency = new int [26]; int len = str.Length; for ( int i = 0; i < len; i++) { // for each character // increment its frequency // in the frequency array frequency[str[i]- 'a' ]++; } // stores a single copy // of a string, which on // repeating forms a k-string String single_copy = "" ; // iterate over // frequency array for ( int i = 0; i < 26; i++) { // if the character occurs // in the string, check if // it is divisible by k, // if not divisible then // k-string cant be formed if (frequency[i] != 0) { if ((frequency[i] % k) != 0) { String ans = "Not Possible" ; return ans; } else { // ith character occurs // (frequency[i]/k) times in // a single copy of k-string int total_occurrences = (frequency[i] / k); for ( int j = 0; j < total_occurrences; j++) { single_copy += ( char )(i + 97); } } } } String kString = "" ; // append the single // copy formed k times for ( int i = 0; i < k; i++) { kString += single_copy; } return kString; } // Driver Code public static void Main(String[] args) { String str = "gkeekgee" ; int K = 2; String kString = kStringGenerate(str, K); Console.Write(kString); } } // This code is contributed by Princi Singh |
Javascript
<script> // JavaScript program to form a // K-Concatenated-String // from a given string // Function to print // the k-concatenated string function kStringGenerate(str, k) { // maintain a frequency table // for lowercase letters var frequency = new Array(26).fill(0); var len = str.length; for ( var i = 0; i < len; i++) { // for each character // increment its frequency // in the frequency array frequency[str[i].charCodeAt(0) - "a" .charCodeAt(0)]++; } // stores a single copy // of a string, which on // repeating forms a k-string var single_copy = "" ; // iterate over // frequency array for ( var i = 0; i < 26; i++) { // if the character occurs // in the string, check if // it is divisible by k, // if not divisible then // k-string cant be formed if (frequency[i] != 0) { if (frequency[i] % k != 0) { var ans = "Not Possible" ; return ans; } else { // ith character occurs // (frequency[i]/k) times in // a single copy of k-string var total_occurrences = parseInt(frequency[i] / k); for ( var j = 0; j < total_occurrences; j++) { single_copy += String.fromCharCode(i + 97); } } } } var kString = "" ; // append the single // copy formed k times for ( var i = 0; i < k; i++) { kString += single_copy; } return kString; } // Driver Code var str = "gkeekgee" ; var K = 2; var kString = kStringGenerate(str, K); document.write(kString); </script> |
eegkeegk
Time Complexity: O(N), Here N is the length of the string.
Auxiliary Space: O(N), Here N is the length of the string.