304 North Cardinal St.
Dorchester Center, MA 02124

# Rely even indices of String whose prefix has prime variety of distinct Characters

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 full depend of distinct characters within the index vary [0, i] is a first-rate quantity.

Examples:

Enter: N = 6, S = “aabagh”
Output:  2
Clarification: Characters at index 2 and 4 are invalid as 2 and 4 each are even and depend of distict characters upto index 2 and 4 are 2 and three respectively which is prime.

Enter: N = 2, S = “gg”
Output:
Clarification: No invalid character

Strategy: This drawback may 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 test for the required situations  at each character.

Observe the beneath steps to unravel the issue:

• Create a precompute perform and calculate all prime elements 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 test the next:
• The variety of distinct characters within the prefix is prime
• Whether it is true, then incremented the ans by 1.

Under is the implementation of the above strategy.

## C++

 ` `  `#embody ` `utilizing` `namespace` `std;` ` `  `int` `test = 0;` `int` `isPrime[100001];` ` `  `void` `pre()` `{` `    ``test = 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` `resolve(``int` `N, string S)` `{` `    ` `    ` `    ` `    ``if` `(!test)` `        ``pre();` `    ``int` `dis = 0;` `    ``int` `ans = 0;` ` `  `    ` `    ``unordered_map<``char``, ``int``> f;` `    ``for` `(``int` `i = 0; i < N; i++) {` ` `  `        ` `        ` `        ``if` `(f[S[i]] == 0) {` `            ``f[S[i]]++;` `            ``dis++;` `        ``}` ` `  `        ` `        ` `        ` `        ``if` `(((i % 2) == 0) and isPrime[dis]) {` `            ``ans++;` `        ``}` `    ``}` `    ``return` `ans;` `}` ` `  `int` `fundamental()` `{` `    ``int` `N = 6;` `    ``string S = ``"aabagh"``;` ` `  `    ` `    ``cout << resolve(N, S) << endl;` ` `  `    ``return` `0;` `}`

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