You are not logged in. Please login at www.codechef.com 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, 21:30

vivek96's gravatar image

2★vivek96
518110
accept rate: 7%

edited 22 Nov, 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

      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.

link

answered 23 Nov, 12:32

vivek_1998299's gravatar image

5★vivek_1998299
674
accept rate: 5%

edited 23 Nov, 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:
         break
      myDict[s [j]] = 1
      print s [i:j+1]
link

answered 23 Nov, 18:00

aayushkapadia's gravatar image

6★aayushkapadia
4356
accept rate: 12%

edited 23 Nov, 18:07

Oohk I think i misread the question.

Thanks for correcting.

(23 Nov, 18:55) vivek_19982995★
toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×1,972
×1,469
×2

question asked: 12 Oct, 21:30

question was seen: 213 times

last updated: 23 Nov, 18:59