You are not logged in. Please login at to post your questions!


write a program to generate unique substrings(contains only unique characters) of given string.

please suggest efficient solution.

asked 12 Oct '17, 21:30

vivek96's gravatar image

accept rate: 7%

edited 22 Nov '17, 20:23

I am assuming that you want to generate distinct substrings of a string. U could do this using trie in O(N^2) Just insert all suffix of the string in trie,and then count the number of nodes is trie.To get the strings u can do dfs.

lets say abba Suffix-abba,bba,ba,a Insert


       / \

      a. b

     /    \

    b.    b

  /         \

 b.          a



Ans 7

Edit:- Sorry i misread the question.If the substring can have only unique characters then u can do simple bruteforce as @ayushkapadia said.


answered 23 Nov '17, 12:32

vivek_1998299's gravatar image

accept rate: 23%

edited 23 Nov '17, 18:59

If you want to generate substrings which have only unique characters, then it is very simple done in O (N X 26). As the length of that substring will not be greater than 26 according to pegion hole principle. So just do the brute force that is for every i loop over all j greater than i, but stop whenever you see a repeated character.I am not considering printing time here.But in the worst case it will be O (26 X 26 X N).

for i in range (0,n):
   myDict = dict ()
   for j in range (i,n):
      if s [j] in myDict:
      myDict[s [j]] = 1
      print s [i:j+1]

answered 23 Nov '17, 18:00

aayushkapadia's gravatar image

accept rate: 12%

edited 23 Nov '17, 18:07

Oohk I think i misread the question.

Thanks for correcting.

(23 Nov '17, 18:55) vivek_19982996★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 12 Oct '17, 21:30

question was seen: 510 times

last updated: 23 Nov '17, 18:59