Question

How many unique substrings are there in the word "christmas"?

Answer 1

Define unique sub-string.

Answer 2

a subset of the characters in the original word, in their original order

Answer 3

Letters would be repeated ?

Answer 4

think of it this way, take the original word, cross out as many letters as you want, combine those that remain. how many unique words can you make this way?

Answer 5

\( 2^n-1 \) ? For all different letters.

Answer 6

no it's not!

Answer 7

but there's a repeated letter S ... chris is just one word but can be made two ways so shouldn't be counted twice

Answer 8

Then you have to compute the sum individually.

Answer 9

Chosing 1 letter , 2 letter , 3 letters, ....

Answer 10

I can solve it using generating functions.

Answer 11

It seems like that might be one of the ways to tackle this. Doing cases for how many letters are in the substring.

Answer 12

Or maybe you can do three cases, when there are no S's, one S and two S's. That might be a little easier to manage.

Answer 13

The brute force way is just to enumerate all 2^9 substrings and eliminate duplicates; I was wondering if there was something more elegant.

Answer 14

I still believe that generating function would be good way to solve this.

Answer 15

oh you want to generate them ? Then you need suffix tree ( http://en.wikipedia.org/wiki/Suffix_tree)

Answer 16

It's in linear time.

Answer 17

When you say unique substring, order is important as well right? Like Chris and hcirs are different?

Answer 18

we're just talking about 2^9 so generating them won't take long, i was just wondering if there was a clever analysis.

Answer 19

the way I've defined it, hcirs is not a valid substring. I am not allowing permutations.

Answer 20

unique sub-string means the orders in the actual string is preserved...

Answer 21

so, hcirs = Chris

Answer 22

oh oh oh oh. this is no where near as bad as I was thinking then. Forgive me for not knowing the jargon.

Answer 23

Just choose .. 1, 2,3,4,5,6,7,8,9 and sum them up.

Answer 24

well, yes, that's the brute force way, enumerate all 2^9 possible substrings and then eliminate duplicates. I'm wondering if there's a way to analyze the number that will result without enumerating them by brute force.

Answer 25

no that's not brue force way.

Answer 26

sure it is.

Answer 27

do you know :

if a things of one kind, b things of second and c things of third kind and so on, then how many ways of choosing r objects out of these ?

combinatorically not bruteforce.

Answer 28

I'm not sure what you mean, a*b*c doesn't preserve order.

I'm saying the guaranteed-correct, but not-very-smart way to solve this problem is just to enumerate every possible substring (there are only 511 of them) and count how many unique ones there are in the list

Answer 29

a is a variable.

Answer 30

what i'm wondering is if there's a more clever way to solve it other than enumerating every possibility

Answer 31

There is a clever way and I already told you ..

Answer 32

how?

Answer 33

do you know how are we get \( 2^n \) subset of a set having exactly \( n \) elements? The combinatoric prove.

Answer 34

getting*

Answer 35

there are repeated letters so that doesn't give the correct answer

Answer 36

Why don't you listen to me ? you don't know the basics even.

Answer 37

if the letters were all unique then yes, there would be 2^9-1 possible unique substrings. but in this case, the letter 'S' appears twice so that reduces the number of unique substrings. my question is, by how many?

Answer 38

you are not making any sense

Answer 39

I am making complete sense.

Answer 40

let's try with a smaller word so you can understand what i'm saying -- how many unique substrings are there of the word "sas"?

Answer 41

okay .. that number 2^n do you know we are getting it ?

Answer 42

yes

Answer 43

tell me ..

Answer 44

i understand, for the 3rd time, that 2^n gives you the number of substrings if every string were unique. i'm trying to explain to you why that analysis fails if the letters are not all unique.

tell me, what does your method say are the number of unique substrings in the string "sas"?

Answer 45

Oh nooooo I know this analysis fails.. but the process of developing the analysis works here too.

Answer 46

So, do you know how we get 2^n combinatorically ?

Answer 47

yes obviously i know that

Answer 48

tell me ..

Answer 49

if you had an n-letter word where each letter were unique, you could consider each letter one bit of an n-bit number, where 0 indicates the letter is absent and 1 indicates it is present. each n-bit number (from 0..2^n-1) is a unique substring.

what i keep trying to explain is that this analysis does not work if a letter appears more than once!

Answer 50

Oh you don't know the combinatorial proof.

Answer 51

explain it then

Answer 52

If you have n letter word then the number of subset of it given by \( \sum \limits_{k=0}^n \binom{n}{k} = 2^n\) since we ignore the empty subset for some analysis we ignore k =1 and we write \( \sum \limits_{k=1}^n \binom{n}{k} = 2^n -1 \)

Answer 53

The same analysis works here, but choosing r items from n non-distinct items requires generating functions.

Answer 54

i think you are missing a subtlety to the problem, which is what i keep trying to explain: the distance between the repeated letters matters. the number of unique substrings for "abcdee" is different than "eabcde" even though they have the same letters.

Answer 55

"abcdee" has a large number of non-unique strings because any string that ends with 'e' can just as easily end with the first e or the second, and the two are indistinguishable

Answer 56

but that is not true of the case where the repeated letters are at the beginning and the end

Answer 57

just choosing the letters to be included and excluded doesn't take into account these differences

Answer 58

Alright, fair enough.

Then there is only O(n+L) algorithm that I can do using suffix tree.

Answer 59

for example "sas" can generate s, sa, sas, ss, and as. but "ssa" can only generate s, sa, ss, and ssa. 4 words vs 5 even though the letters are the same.

Answer 60

I am sure no closed form is possible with that constraints.

Answer 61

i agree there is no closed form generally. but a friend and i on the whiteboard today thought the answer might be 2^9 - 2^4 - 1 specifically for the word "christmas", because the two s's generate repeats only when "tma" is excluded, leaving all combinations of "chri" (2^4) as repeats. i was curious to see if someone here might also come up with the same number.

Answer 62

in any case, thanks for the discussion.

Answer 63

you are welcome.