×

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

 0 please suggest efficient solution. asked 12 Oct '17, 21:30 2★vivek96 518●2●15 accept rate: 7%

 0 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  Root / \ a. b / \ b. b / \ b. a /  a Ans 7 a,ab,abb,abba,b,bb,bba  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 1.5k●2●9 accept rate: 23%
 0 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: break myDict[s [j]] = 1 print s [i:j+1]  answered 23 Nov '17, 18:00 435●6 accept rate: 12% Oohk I think i misread the question. Thanks for correcting. (23 Nov '17, 18:55)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×2,508
×1,617
×2

question asked: 12 Oct '17, 21:30

question was seen: 510 times

last updated: 23 Nov '17, 18:59