String which when repeated exactly K times gives a permutation of S
Given an integer K and a string str of lowercase English characters, the task is to find a string s such that when s is repeated exactly K times, it gives a permutation of S. If no such string exists, print -1.
Examples:
Input: str = “aabb”, k = 2
Output: ab
“ab” when repeated 2 times gives “abab” which is a permutation of “aabb”Input: str = “aabb”, k = 3
Output: -1
Approach 1 : Using Map and Sorting
In this approach, we will make use of a map to store the frequency of each character in the string.
We will then sort the map based on the frequency of the characters in decreasing order. Finally, we
will iterate through the map and check if the frequency of each character is divisible by k. If yes,
then we will append the character to the answer string k times. If any character's frequency is not
divisible by k, we return -1.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Function to return a string which when repeated // exactly k times gives a permutation of s string K_String(string s, int k) { // size of string int n = s.size(); // map to store frequency of each character map< char , int > freq; // get frequency of each character for ( int i = 0; i < n; i++) freq[s[i]]++; // to store final answer string str = "" ; // sort the map based on frequency in decreasing order vector<pair< char , int > > sorted_freq(freq.begin(), freq.end()); sort(sorted_freq.begin(), sorted_freq.end(), []( const pair< char , int >& a, const pair< char , int >& b) { return a.second > b.second; }); // iterate through the sorted map for ( auto it : sorted_freq) { char c = it.first; int f = it.second; // check if frequency is divisible by k if (f % k == 0) { int x = f / k; // add to answer while (x--) { str += c; } } // if frequency is not divisible by k else { return "-1" ; } } return str; } // Driver code int main() { string s = "aabb" ; int k = 2; // function call cout << K_String(s, k); return 0; } |
Java
import java.util.*; public class Main { // Function to return a string which when repeated // exactly k times gives a permutation of s public static String K_String(String s, int k) { // size of string int n = s.length(); // map to store frequency of each character Map<Character, Integer> freq = new HashMap<>(); // get frequency of each character for ( int i = 0 ; i < n; i++) { char c = s.charAt(i); freq.put(c, freq.getOrDefault(c, 0 ) + 1 ); } // to store final answer StringBuilder str = new StringBuilder(); // sort the map based on frequency in decreasing // order List<Map.Entry<Character, Integer> > sorted_freq = new ArrayList<>(freq.entrySet()); Collections.sort( sorted_freq, new Comparator< Map.Entry<Character, Integer> >() { @Override public int compare( Map.Entry<Character, Integer> a, Map.Entry<Character, Integer> b) { return b.getValue().compareTo( a.getValue()); } }); // iterate through the sorted map for (Map.Entry<Character, Integer> entry : sorted_freq) { char c = entry.getKey(); int f = entry.getValue(); // check if frequency is divisible by k if (f % k == 0 ) { int x = f / k; // add to answer while (x-- > 0 ) { str.append(c); } } // if frequency is not divisible by k else { return "-1" ; } } return str.toString(); } // Driver code public static void main(String[] args) { String s = "aabb" ; int k = 2 ; // function call System.out.println(K_String(s, k)); } } |
Python3
# Function to return a string which when repeated # exactly k times gives a permutation of s def K_String(s, k): # size of string n = len (s) # map to store frequency of each character freq = {} # get frequency of each character for i in range (n): if s[i] in freq: freq[s[i]] + = 1 else : freq[s[i]] = 1 # to store final answer str = "" # sort the map based on frequency in decreasing order sorted_freq = sorted (freq.items(), key = lambda x: x[ 1 ], reverse = True ) # iterate through the sorted map for it in sorted_freq: c = it[ 0 ] f = it[ 1 ] # check if frequency is divisible by k if f % k = = 0 : x = f / / k # add to answer while x > 0 : str + = c x - = 1 # if frequency is not divisible by k else : return "-1" return str # Driver code s = "aabb" k = 2 # function call print (K_String(s, k)) |
C#
using System; using System.Collections.Generic; using System.Linq; public class MainClass { public static string K_String( string s, int k) { int n = s.Length; Dictionary< char , int > freq = new Dictionary< char , int >(); // Initialize dictionary with all characters and // frequency 0 foreach ( char c in s) freq = 0; // Update the frequencies foreach ( char c in s) freq++; string str = "" ; var sorted_freq = freq.OrderByDescending(item => item.Value); foreach ( var item in sorted_freq) { char c = item.Key; int f = item.Value; if (f % k == 0) { int x = f / k; while (x > 0) { str += c; x--; } } else { return "-1" ; } } return str; } public static void Main( string [] args) { string s = "aabb" ; int k = 2; Console.WriteLine(K_String(s, k)); } } |
Javascript
// Function to return a string which when repeated // exactly k times gives a permutation of s function K_String(s, k) { // size of string let n = s.length; // map to store frequency of each character let freq = new Map(); // get frequency of each character for (let i = 0; i < n; i++) { if (freq.has(s[i])) { freq.set(s[i], freq.get(s[i]) + 1); } else { freq.set(s[i], 1); } } // to store final answer let str = "" ; // sort the map based on frequency in decreasing order let sorted_freq = Array.from(freq.entries()); sorted_freq.sort((a, b) => b[1] - a[1]); // iterate through the sorted map for (let it of sorted_freq) { let c = it[0]; let f = it[1]; // check if frequency is divisible by k if (f % k === 0) { let x = f / k; // add to answer while (x--) { str += c; } } // if frequency is not divisible by k else { return "-1" ; } } return str; } let s = "aabb" ; let k = 2; // function call console.log(K_String(s, k)); |
Output :
ab
Time Complexity: O(nlogn)
Auxiliary Space: O(n)
Approach 2: An efficient approach is to count the frequency of each character of the given string. If the frequency of any character is not divisible by k then the solution is not possible and print -1. Otherwise, add every character (frequency / k) times to the resultant string and print the generated string in the end.
Below is the implementation of the above approach:
C++
// C++ program to find a string which when repeated // exactly k times gives a permutation // of the given string #include <bits/stdc++.h> using namespace std; // Function to return a string which when repeated // exactly k times gives a permutation of s string K_String(string s, int k) { // size of string int n = s.size(); // to frequency of each character int fre[26] = { 0 }; // get frequency of each character for ( int i = 0; i < n; i++) fre[s[i] - 'a' ]++; // to store final answer string str = "" ; for ( int i = 0; i < 26; i++) { // check if frequency is divisible by k if (fre[i] % k == 0) { int x = fre[i] / k; // add to answer while (x--) { str += ( char )(i + 'a' ); } } // if frequency is not divisible by k else { return "-1" ; } } return str; } // Driver code int main() { string s = "aabb" ; int k = 2; // function call cout << K_String(s, k); return 0; } |
Java
// Java program to find a string which when repeated // exactly k times gives a permutation // of the given string class GfG { // Function to return a string which when repeated // exactly k times gives a permutation of s static String K_String(String s, int k) { // size of string int n = s.length(); // to frequency of each character int fre[] = new int [ 26 ]; // get frequency of each character for ( int i = 0 ; i < n; i++) fre[s.charAt(i) - 'a' ]++; // to store final answer String str = "" ; for ( int i = 0 ; i < 26 ; i++) { // check if frequency is divisible by k if (fre[i] % k == 0 ) { int x = fre[i] / k; // add to answer while (x != 0 ) { str += ( char )(i + 'a' ); x--; } } // if frequency is not divisible by k else { return "-1" ; } } return str; } // Driver code public static void main(String[] args) { String s = "aabb" ; int k = 2 ; // function call System.out.println(K_String(s, k)); } } |
Python 3
# Python 3 program to find a string # which when repeated exactly k times # gives a permutation of the given string # Function to return a string which # when repeated exactly k times gives # a permutation of s def K_String(s, k): # size of string n = len (s) # to frequency of each character fre = [ 0 ] * 26 # get frequency of each character for i in range (n): fre[ ord (s[i]) - ord ( 'a' )] + = 1 # to store final answer str = "" for i in range ( 26 ): # check if frequency is divisible by k if (fre[i] % k = = 0 ): x = fre[i] / / k # add to answer while (x): str + = chr (i + ord ( 'a' )) x - = 1 # if frequency is not divisible by k else : return "-1" return str # Driver code if __name__ = = "__main__" : s = "aabb" k = 2 # function call print (K_String(s, k)) # This code is contributed # by ChitraNayal |
C#
// C# program to find a string which // when repeated exactly k times gives // a permutation of the given string using System; class GFG { // Function to return a string which // when repeated exactly k times gives // a permutation of s static String K_String(String s, int k) { // size of string int n = s.Length; // to frequency of each character int [] fre = new int [26]; // get frequency of each character for ( int i = 0; i < n; i++) fre[s[i] - 'a' ]++; // to store final answer String str = "" ; for ( int i = 0; i < 26; i++) { // check if frequency is // divisible by k if (fre[i] % k == 0) { int x = fre[i] / k; // add to answer while (x != 0) { str += ( char )(i + 'a' ); x--; } } // if frequency is not divisible by k else { return "-1" ; } } return str; } // Driver code public static void Main(String[] args) { String s = "aabb" ; int k = 2; // function call Console.WriteLine(K_String(s, k)); } } // This code is contributed by Arnab Kundu |
Javascript
<script> // Javascript program to find a string which when repeated // exactly k times gives a permutation // of the given string // Function to return a string which when repeated // exactly k times gives a permutation of s function K_String(s,k) { // size of string let n = s.length; // to frequency of each character let fre = new Array(26); for (let i=0;i<fre.length;i++) { fre[i]=0; } // get frequency of each character for (let i = 0; i < n; i++) fre[s[i].charCodeAt(0) - 'a' .charCodeAt(0)]++; // to store final answer let str = "" ; for (let i = 0; i < 26; i++) { // check if frequency is divisible by k if (fre[i] % k == 0) { let x = Math.floor(fre[i] / k); // add to answer while (x != 0) { str += String.fromCharCode(i + 'a' .charCodeAt(0)); x--; } } // if frequency is not divisible by k else { return "-1" ; } } return str; } // Driver code let s = "aabb" ; let k = 2; // function call document.write(K_String(s, k)); //This code is contributed by avanitrachhadiya2155 </script> |
PHP
<?php // PHP program to find a string which // when repeated exactly k times gives // a permutation of the given string // Function to return a string which // when repeated exactly k times gives // a permutation of s function K_String( $s , $k ) { // size of string $n = strlen ( $s ); // to frequency of each character $fre = $array = array_fill (0, 26, 0); // get frequency of each character for ( $i = 0; $i < $n ; $i ++) $fre [ord( $s [ $i ]) - ord( 'a' )]++; // to store final answer $str = "" ; for ( $i = 0; $i < 26; $i ++) { // check if frequency is divisible by k if ( $fre [ $i ] % $k == 0) { $x = $fre [ $i ] / $k ; // add to answer while ( $x --) { $str .= chr ( $i + ord( 'a' )); } } // if frequency is not divisible by k else { return "-1" ; } } return $str ; } // Driver code $s = "aabb" ; $k = 2; // function call echo K_String( $s , $k ); // This code is contributed by Ryuga ?> |
ab
Time Complexity: O(n)
Space Complexity: O(1)
Contact Us