Shortest Non-repeating Substring
Given an alphanumeric string, find the shortest substring that occurs exactly once as a (contiguous) substring in it. Overlapping occurrences are counted as distinct. If there are several candidates of the same length, you must output all of them in the order of occurrence. The space is NOT considered as a valid non-repeating substring.
Consider the following cases:
Case 1: If the given string is
asdfsasa, the answer should be
Case 2: If the given string is
the answer should be
['sa', 'ad', 'da', 'na', 'nd', 'ds']
Case 3: If the given string is
wwwwwwww, the answer should be
Here is my solution in Python.
It is quite brute force. I am not sure about the order of
rfind() built-in methods
in Python. Assuming these are $O(n)$, my algorithm is in $O(n^3)$. Please put your answers in
comments below, if your answer has a better scaling.
The function definition that I use for finding non-empty non-repeating strings is recursive.
I call this method as follows to get the desired results:
A similar solution can also be written in
C++. The corresponding
methods in JAVA are called
lastIndexOf(), respectively. In C++, these methods are
called same as in Python.
Please feel free to put your method definition in any programming language.