Count even indices of String whose prefix has prime number of distinct Characters – GeeksforGeeks

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 distict 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.

Time Complexity: O(N√N)
Auxiliary Space: O(N)

Related Articles: