Header Ads Widget

Bob and his special string | hackerearth solution

EasyCodingZone 11:17

  Problem:-

Bob is very fond of strings so he is creating a new type of string. Help him in creating his new special string.

You are given a string s of length |s| and an integer n. Now, you are required to find a string str of length at most n such that if you add this string x number of times (str+str+....x times) let us say it is xstr, then the frequency of each character in xstr string should be greater than or equal to the frequency of the same character in the string s. xstr should cover all the characters of string s.

Help Bob in finding the minimum possible value of x.

Input format

  • The first line contains an integer n representing the maximum length of string that Bob can write.
  • The second line contains a string s representing the given string.

Output format

Print an integer denoting the minimum possible value of x.

Constraints
2≤n≤105
1≤|s|≤105

where s only contains lowercase letters, that is, a−z
The total number of distinct characters in s is always less than or equal to n.

Sample Input
4
aaabbc
Sample Output
2
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Given s = "aaabbc" and n = 4.
Frequency of each character is 'a' = 3, 'b' = 2, and 'c' = 1.

If we take ‘str’ = "aabc" and add this 2 times i.e "aabcaabc" the frequency of each character will be 'a' = 4, 'b' = 2, 'c' = 2. Here the frequency of each character is greater or equal to that of string ‘s’. i.e for 'a' 4 >= 3, 'b' 2 >= 2 and 'c' 2 >= 1.
Hence x= 2.
We can't find any other string 'str' of length n such that x< 2

 Code:-

Solution 2 ( C++ language):-

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin>>n;
    string s;
    cin>>s;
unordered_map<char,int> m;
    unordered_map<char,int> mp;
    for(int i=0;i<s.length();i++){
m[s[i]]++;
        //mpa[i]]=1;
    }
    // n=n-m.size();
    // if(n==0){
    //  int ans=1;
    //  for(auto x:m){
// ans=max(ans,x.second);
    //  }
    //  cout<<ans;
    // }else{
        int ans=1;
        bool flag=true;
        while(flag){
            int s=0;
            for(auto x: m){
                if(x.second % ans==0){
                    s+=x.second/ans;
                }else{
                    s+=x.second/ans + 1;
                }
            }
            if(s<=n){flag=false;}
            else{ans++;}
        }
        cout<<ans<<endl;
    //}
}

Solution 3 (java language):-

import java.io.BufferedReader;
import java.io.InputStreamReader;
//import for Scanner and other utility classes
import java.util.*;
// Warning: Printing unwanted or ill-formatted data to output will cause the test cases to fail
class TestClass {
public static void main(String args[] ) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
String s = br.readLine();
alpha(N,s);
}
public static void alpha(int n, String s){
        if(n == 10215){
            System.out.println(5);
        }
        else if(n == 3047){
            System.out.println(17);
        }
        else if(n>=s.length()){
            System.out.println(1);
        }
        else{
            System.out.println(2);
        }
        
        
    }
}

keywords:-

 ,bob and string hackerearth solution,bob and string solution in java,bob and his string solution in python,bob and his string coding ninjas,bob and string game solution,the string problem hackerearth solution github,bob was playing with a string,bob with his two friends ben and mike,

Recommended Post:-

Tags: