Given a string S and an integer N, the task is to check if it is possible to generate any string N times from the characters of the given string or not. If it is possible, print Yes. Otherwise, print No.
Examples:
Input: S = “caacbb”, N = 2
Output: Yes
Explanation: All possible strings that can be generated N(= 2) times are {“abc”, “ab”, “aa”, “bb”, “cc”, “bc”, “ca”}Input: S = “cbacbac”, N = 3
Output: No
Explanation: Since none of the characters occurs N times, therefore no string can be generated N times from the characters of the given string.
Naive Approach: The simplest approach to solve the problem is to generate all possible permutations of all possible lengths of the given string and check if any permutation occurs N times or not. If found to be true, print “Yes”. Otherwise, print “No”
Time Complexity: O(N*L!), where L is the length of the given string.
Auxiliary Space: O(L)
Efficient Approach: The idea is to store the frequency of all characters and count the number of characters occurring at least N times. Follow the steps below to solve the problem:
- Store the frequencies of each character of the string in an array, say freq[].
- Traverse the freq[] array and for every ith Character, check if freq[i] >= N or not.
- If any character is found to be satisfying the above condition, print Yes. Otherwise, print No.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if the freq of// any character is divisible by Nbool isSame(string str, int n){ // Stores the frequency of characters map<int, int> mp; for (int i = 0; i < str.length(); i++) { mp[str[i] - 'a']++; } for (auto it : mp) { // If frequency of a character // is not divisible by n if ((it.second) >= n) { return true; } } // If no character has frequency // at least N return false;}// Driver Codeint main(){ string str = "ccabcba"; int n = 4; // Function Call if (isSame(str, n)) { cout << "Yes"; } else { cout << "No"; }} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to check if the freq of// any character is divisible by Nstatic boolean isSame(String str, int n){ // Stores the frequency of characters HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); for (int i = 0; i < str.length(); i++) { if(mp.containsKey(str.charAt(i) - 'a')) { mp.put(str.charAt(i) - 'a', mp.get(str.charAt(i) - 'a') + 1); } else { mp.put(str.charAt(i) - 'a', 1); } } for (Map.Entry<Integer, Integer> it : mp.entrySet()) { // If frequency of a character // is not divisible by n if ((it.getValue()) >= n) { return true; } } // If no character has frequency // at least N return false;}// Driver Codepublic static void main(String[] args){ String str = "ccabcba"; int n = 4; // Function Call if (isSame(str, n)) { System.out.print("Yes"); } else { System.out.print("No"); }}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach from collections import defaultdict# Function to check if the freq of# any character is divisible by N def isSame(str, n): # Stores the frequency of characters mp = defaultdict(lambda : 0) for i in range(len(str)): mp[ord(str[i]) - ord('a')] += 1 for it in mp.keys(): # If frequency of a character # is not divisible by n if(mp[it] >= n): return True # If no character has frequency # at least N return False# Driver Codestr = "ccabcba"n = 4# Function callif(isSame(str, n)): print("Yes")else: print("No")# This code is contributed by Shivam Singh |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to check if the freq of// any character is divisible by Nstatic bool isSame(String str, int n){ // Stores the frequency of characters Dictionary<int, int> mp = new Dictionary<int, int>(); for (int i = 0; i < str.Length; i++) { if(mp.ContainsKey(str[i] - 'a')) { mp[str[i] - 'a'] = mp[str[i] - 'a'] + 1; } else { mp.Add(str[i] - 'a', 1); } } foreach (KeyValuePair<int, int> it in mp) { // If frequency of a character // is not divisible by n if ((it.Value) >= n) { return true; } } // If no character has frequency // at least N return false;}// Driver Codepublic static void Main(String[] args){ String str = "ccabcba"; int n = 4; // Function Call if (isSame(str, n)) { Console.Write("Yes"); } else { Console.Write("No"); }}}// This code is contributed by shikhasingrajput |
Javascript
<script>// JavaScript program for the above approach// Function to check if the freq of// any character is divisible by Nfunction isSame(str, n){ // Stores the frequency of characters var mp = {}; for(var i = 0; i < str.length; i++) { if (mp.hasOwnProperty(str[i].charCodeAt(0) - "a".charCodeAt(0))) { mp[str[i].charCodeAt(0) - "a".charCodeAt(0)] = mp[str[i].charCodeAt(0) - "a".charCodeAt(0)] + 1; } else { mp[str[i].charCodeAt(0) - "a".charCodeAt(0)] = 1; } } for(const [key, value] of Object.entries(mp)) { // If frequency of a character // is not divisible by n if (value >= n) { return true; } } // If no character has frequency // at least N return false;}// Driver Codevar str = "ccabcba";var n = 4;// Function Callif (isSame(str, n)){ document.write("Yes");} else{ document.write("No");}// This code is contributed by rdtank</script> |
No
Time Complexity: O(L), where L is the length of the given string
Auxiliary Space: O(L)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
