Software Engineer

You are given a string 'S' of length 'N' consisting of lowercase English letters. You want all substrings of the string 'S' to be distinct. You are allowed to change characters at some positions to some other lowercase English letters.

You have to find the minimum number of changes required to make all the substrings of the string distinct or return -1 if you can't make it.

A substring is a contiguous subsegment of a string. For example, "acab" is a substring of "abacaba" (it starts in position 3 and ends in position 6), but "aa" or "d" aren't substrings of this string.

Hint:

Think about substrings of length one.

For Example:-

Let 'N' = 3, 'S' = "aac".
You can change characters at index 2 to some other character (1-based indexing).
Like 'S' = "abc".
All substrings of 'S' are "a", "b", "c", "ab", "bc", "abc", all of which are distinct.
So the answer is 1.

You are given a positive integer ‘N’. Your task is to print all prime numbers less than or equal to N.

Note: A prime number is a natural number that is divisible only by 1 and itself. Example - 2, 3, 17, etc.

You can assume that the value of N will always be greater than 1. So, the answer will always exist.