Prime String

Alice has just learned about primeStrings. 

A string is a primeString if the number of distinct alphabets used in the string is a prime and also the number of occurrences of each alphabet in the string is also a prime.
Given a String you need to tell if it is a primeString or not.

Example:

Input:  s = "ababb"
Output: YES

Approach

C++

#include <bits/stdc++.h>
using namespace std;

//function to check for prime number
bool isprime(int n)
{
    if (n <= 1)
        return false;
    for (int i = 2i <= sqrt(n); i++)
        if (n % i == 0)
            return false;
    return true;
}

bool primeString(string s)
{
    int n = s.size();
    int f[26] = {0};
    for (int i = 0i < ni++)
        f[s[i] - 'a']++;
    int sum = 0;
    for (int i = 0i < 26i++)
        if (f[i] > 0)
            sum++;
    if (isprime(sum))
    {
        int flag = 0;
        for (int i = 0i < 26i++)
        {
            if (f[i] > 0)
            {
                if (!isprime(f[i]))
                {
                    flag = 1;
                    break;
                }
            }
        }
        if (flag == 0)
            return true;
        else
            return false;
    }
    else
        return false;
}
int main()
{

    string s = "ababb";

    if (primeString(s))
        cout << "YES\n";
    else
        cout << "NO\n";
    return 0;
}


No comments:

Post a Comment