Smallest substring occurring only once in a given string

Smallest substring occurring only once in a given string

Given a string S consisting of N lowercase alphabets, the task is to find the length of the smallest substring in S whose occurrence is exactly 1.

Examples:

Input: S = “abaaba”
Output: 2
Explanation: 
The smallest substring in the string S, whose occurrence is exactly 1 is “aa” . Length of this substring is 2.
Therefore, print 2.

Input: S = “zyzyzyz”
Output: 5

Approach: To solve the problem, the idea is to generate all possible substring of the given string S and store the frequency of each substring in a HashMap. Now, traverse the HashMap and print the substring of minimum length whose frequency is 1. 

Below is the implementation of the above approach:

Python3

from collections import Counter    def smallestSubstring(a):               a1 = []                   for i in range(len(a)):         for j in range(i+1, len(a)):                                       if i != j:                                                        a1.append(a[i:j+1])                                    a2 = Counter(a1)       freshlist = []                      for i in a2:                               if a2[i] == 1:                                       freshlist.append(i)                          dictionary = dict()              for i in range(len(freshlist)):                           dictionary[freshlist[i]] = len(freshlist[i])                  newlist = []                 for i in dictionary:           newlist.append(dictionary[i])                     return(min(newlist))     S = "ababaabba" print(smallestSubstring(S))

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

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

Let's block ads! (Why?)