Distinct Substrings

Easy
0/40
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in company
Deloitte

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:- 
First-line contains an integer 'T', which denotes the number of test cases.
For every test case:-
First-line contains an integer 'N', denoting the length of the string 'S'.
Second-line contains the string 'S'.
Output Format:- 
For each test case, Return the minimum number of changes required to make all the substrings of the string distinct or return -1 if you can't make it.
Note:- 
You don’t need to print anything. Just implement the given function.
Constraints:- 
1 <= 'T' <= 10
1 <= 'N' <= 10^5
'S' consists only of lower case english alphabets

The Sum of 'N' overall test cases does not exceed 10^5.
Time Limit: 1 sec
Constraints:-
1 <= 'T' <= 10
1 <= 'N' <= 10^5
'S' consists only of lower case english alphabets

The Sum of 'N' overall test cases does not exceed 10^5.
Time Limit: 1 sec
Sample Input 1:-
2
3
abc
4
xxyz
Sample Output 1:-
0
1
Explanation of sample input 1:-
First test case:-
No changes are required.
So the answer is 0.

Second test case:-
You can change the character at index 1 to some other character (1-based indexing).
Like 'S'="bxyz".
So the answer is 1.
Sample Input 2:-
2
4
bbbb
8
abcdabcd
Sample Output 2:-
3
4
Hint

Can we make all the substrings of the string ‘S’ distinct if 'N' is greater than 26?

Approaches (1)
Strings

Approach:-

 

  • If 'N' is greater than 26, then return -1, as we don't have more than 26 distinct lowercase English alphabets.
  • To make the substrings distinct, we have to make the characters of the string distinct.
  • We can change the repeating characters to any other character.
  • The number of characters we have to change is 'N' - unique characters in string 'S'.


 

 Algorithm:-

 

  • If 'N' is greater than 26, then return -1, as we don't have more than 26 distinct lowercase English alphabets.
  • Create an array of size 26 named ‘occ’.
  • Iterate using 'i' from 1 to 'N' in the string 'S'.
    • Update, occ[S[i] - 'a']++.
  • Initialize a variable 'unique' with 0.
  • Iterate using 'i' from 1 to 26 in array 'occ'.
    • If 'occ[i]' > 0, then increase 'unique' by 1.
  • Return 'N' - 'unique' which are repeating characters we have to change.
Time Complexity

O(N), where ‘N’ is the length of the string ‘S’.
 

We are traversing the string 'S' of length 'N', So The Time Complexity is O(N).

Space Complexity

O(1).

 

We are creating an array 'occ' of size 26, So the Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Distinct Substrings
Full screen
Console