Given a string S of dimension N. The duty is to seek out the variety of Invalid characters. Index i (0 ≤ i < N) is invalid if i is even and the overall rely of distinct characters within the index vary [0, i] is a first-rate quantity.
Enter: N = 6, S = “aabagh”
Rationalization: Characters at index 2 and 4 are invalid as 2 and 4 each are even and rely of distict characters upto index 2 and 4 are 2 and three respectively which is prime.
Enter: N = 2, S = “gg”
Rationalization: No invalid character
Method: This downside might be solved utilizing the prefix array idea.
Thought: The concept is to precompute all of the prime numbers within the given vary of N after which simply examine for the required situations at each character.
Comply with the beneath steps to resolve the issue:
- Create a precompute operate and calculate all prime components utilizing the sieve of Eratosthenes.
- Create a hashmap to retailer frequencies of characters which can assist us decide if the character is a replica or not.
- Iterate over the string from and when any even index is reached examine the next:
- The variety of distinct characters within the prefix is prime
- Whether it is true, then incremented the ans by 1.
Beneath is the implementation of the above method.
Time Complexity: O(N√N)
Auxiliary Area: O(N)