Given a string S of size N. The task is to find the number of Invalid characters. Index i (0 ? i < N) is invalid if i is even and the total count of distinct characters in the index range [0, i] is a prime number.
Examples:
Input: N = 6, S = “aabagh”
Output: 2
Explanation: Characters at index 2 and 4 are invalid as 2 and 4 both are even and count of distinct characters upto index 2 and 4 are 2 and 3 respectively which is prime.Input: N = 2, S = “gg”
Output: 0
Explanation: No invalid character
Approach: This problem can be solved using the prefix array concept.
Idea: The idea is to precompute all the prime numbers in the given range of N and then just check for the required conditions at every character.
Follow the below steps to solve the problem:
- Create a precompute function and calculate all prime factors using the sieve of Eratosthenes.
- Create a hashmap to store frequencies of characters which will help us determine if the character is a duplicate or not.
- Iterate over the string from and when any even index is reached check the following:
- The number of distinct characters in the prefix is prime
- If it is true, then incremented the ans by 1.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;int check = 0;int isPrime[100001];// Precompute all prime numbersvoid pre(){ check = 1; memset(isPrime, 1, sizeof isPrime); isPrime[0] = isPrime[1] = 0; for (int i = 4; i <= 100000; i += 2) isPrime[i] = 0; for (int i = 3; i * i <= 100000; i += 2) { if (isPrime[i]) { for (int j = 3; j * i <= 100000; j += 2) isPrime[i * j] = 0; } }}int solve(int N, string S){ // If running first time then precompute // all numbers otherwise get the result // directly from isPrime array if (!check) pre(); int dis = 0; int ans = 0; // Map to store frequency of a character unordered_map<char, int> f; for (int i = 0; i < N; i++) { // If not visited // mark the character as visited if (f[S[i]] == 0) { f[S[i]]++; dis++; } // If index is even and number of distinct // Characters are also prime increment // the ans by 1 if (((i % 2) == 0) and isPrime[dis]) { ans++; } } return ans;}// Driver codeint main(){ int N = 6; string S = "aabagh"; // Function call cout << solve(N, S) << endl; return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { static int check = 0; static int[] isPrime = new int[100001]; // Precompute all prime numbers static void pre() { check = 1; Arrays.fill(isPrime, 1); isPrime[0] = isPrime[1] = 0; for (int i = 4; i <= 100000; i += 2) isPrime[i] = 0; for (int i = 3; i * i <= 100000; i += 2) { if (isPrime[i] == 1) { for (int j = 3; j * i <= 100000; j += 2) isPrime[i * j] = 0; } } } static int solve(int N, String S) { // If running first time then precompute // all numbers otherwise get the result // directly from isPrime array if (check == 0) { pre(); } int dis = 0; int ans = 0; // Map to store frequency of a character HashMap<Character, Integer> f = new HashMap<>(); for (int i = 0; i < N; i++) { // If not visited // mark the character as visited if (!f.containsKey(S.charAt(i))) { f.put(S.charAt(i), 1); dis++; } // If index is even and number of distinct // Characters are also prime increment // the ans by 1 if ((i % 2 == 0) && (isPrime[dis] == 1)) { ans++; } } return ans; } public static void main(String[] args) { int N = 6; String S = "aabagh"; // Function call System.out.println(solve(N, S)); }}// This code is contributed by lokeshmvs21. |
Python3
# Python3 code to implement the approachimport mathcheck = 0isPrime = []for i in range(0, 100001): isPrime.append(0)# Precompute all prime numbersdef pre(): check = 1 for i in range(0, 100001): isPrime[i] = 1 isPrime[0] = isPrime[1] = 0 for i in range(4, 100001, +2): isPrime[i] = 0 for i in range(3, int(math.sqrt(100000))+1, +2): if (isPrime[i] == 1): for j in range(3, int(10000/i)+1, +2): isPrime[i * j] = 0def solve(N, S): # If running first time then precompute # all numbers otherwise get the result # directly from isPrime array if (check == 0): pre() dis = 0 ans = 0 # Map to store frequency of a character f = {} for i in range(0, N): # If not visited # mark the character as visited if S[i] not in f.keys(): f[S[i]] = 1 dis += 1 # If index is even and number of distinct # Characters are also prime increment # the ans by 1 if ((i % 2 == 0) and (isPrime[dis] == 1)): ans += 1 return ansN = 6S = "aabagh"# Function callprint(solve(N, S))# This code is contributed by ksam24000 |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;class GFG { static int check = 0; static int[] isPrime = new int[100001]; // Precompute all prime numbers static void pre() { check = 1; Array.Fill(isPrime, 1); isPrime[0] = isPrime[1] = 0; for (int i = 4; i <= 100000; i += 2) isPrime[i] = 0; for (int i = 3; i * i <= 100000; i += 2) { if (isPrime[i] == 1) { for (int j = 3; j * i <= 100000; j += 2) isPrime[i * j] = 0; } } } static int solve(int N, string S) { // If running first time then precompute // all numbers otherwise get the result // directly from isPrime array if (check == 0) { pre(); } int dis = 0; int ans = 0; // Map to store frequency of a character Dictionary<char, int> f = new Dictionary<char, int>(); for (int i = 0; i < N; i++) { // If not visited // mark the character as visited if (!f.ContainsKey(S[i])) { f.Add(S[i], 1); dis++; } // If index is even and number of distinct // Characters are also prime increment // the ans by 1 if ((i % 2 == 0) && (isPrime[dis] == 1)) { ans++; } } return ans; } public static void Main() { int N = 6; string S = "aabagh"; // Function call Console.WriteLine(solve(N, S)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
// JavaScript code to implement the approachlet check = 0;let isPrime = new Array(100001).fill(1);// Precompute all prime numbersconst pre = () => { check = 1; isPrime[0] = isPrime[1] = 0; for (let i = 4; i <= 100000; i += 2) isPrime[i] = 0; for (let i = 3; i * i <= 100000; i += 2) { if (isPrime[i]) { for (let j = 3; j * i <= 100000; j += 2) isPrime[i * j] = 0; } }}const solve = (N, S) => { // If running first time then precompute // all numbers otherwise get the result // directly from isPrime array if (!check) pre(); let dis = 0; let ans = 0; // Map to store frequency of a character let f = {}; for (let i = 0; i < N; i++) { // If not visited // mark the character as visited if (!(S[i] in f)) { f[S[i]] = 1; dis++; } // If index is even and number of distinct // Characters are also prime increment // the ans by 1 if (((i % 2) == 0) && isPrime[dis]) { ans++; } } return ans;}// Driver codelet N = 6;let S = "aabagh";// Function callconsole.log(solve(N, S));// This code is contributed by rakeshsahni |
Output
2
Time Complexity: O(N) as pre function is only need to call one time and through which we can solve millions of string so from pre() time is O(1) and solve() travel N time and hasmap give output in O(1) in average case so overall complexity is O(N)
Auxiliary Space: O(N)
Related Articles:
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
