Skip to content## Shortest Non-repeating Substring

#### Examples

#### My Solution

## Similar Articles

— Algorithms, Python — 1 min read

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 `['d', 'f']`

**Case 2:** If the given string is `sadanands`

,

the answer should be `['sa', 'ad', 'da', 'na', 'nd', 'ds']`

**Case 3:** If the given string is `wwwwwwww`

, the answer should be `['wwwwwwww']`

Here is my solution in *Python*.

It is quite brute force. I am not sure about the order of `find()`

and `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*.

`1def findNsubString(s, n):2 subS = []3 for index in range(len(s)+1):4 x = s[index:index+n]5 if s.find(x) == s.rfind(x):6 subS.append(x)7 if subS:8 return subS9 else:10 return findNsubString(s, n+1)`

I call this method as follows to get the desired results:

`1#! /usr/bin/python2import argparse3# Parse Command Line Arguments4parser = argparse.ArgumentParser()5parser.add_argument("-s", "--string", default = "asda", help="Input")6args = parser.parse_args()7s = args.string8# Call Method to find smallest non-repeating sub-string9ans = findNsubString(s, 1)10print(ans)`

A similar solution can also be written in `JAVA`

or `C++`

. The corresponding `find()`

and `rfind()`

methods in JAVA are called `indexOf()`

and `lastIndexOf()`

, respectively. In C++, these methods are
called same as in Python.

Please feel free to put your method definition in any programming language.