Novel finder Program

This was one of the problems that I had faced during one of my interviews. The problem sounded interesting and I was given 1 hour to solve it which I did quite comfortably.

Problem:

The K-doublets of a string of characters are the ordered pairs of characters that are K distance from each other. A string is K-singular if all its K- doublets are different. A string is Novel String if it is K-singular for all possible K distances.

For e.g. take the string FLBL, its 0-doublets are FL, LB and BL. Since all these are different, FLBL is 0-singular. Similarly, its 1-doublets are FB and LL, since they are different FLBL is 1-singular as well. Lastly, the only 2-doublet of FLBL is FL, so FLBL is 2-singular. Hence, FLBL is a Novel String.

Note that the fact that FL is both a 0-doublet and 2-doublet is insignificant as zero and two are different distances.

Input:

The input is one or more non-empty strings of at most 100 capital letters, each string on a line by itself, followed by a line containing only two dollars ($$) signaling the end of the input.

Output:

For each input line, output whether or not it is a Novel string using the exact output format shown below.

Sample Input: (Input File: novel.in)

FLBL

FFLL

ORDINARY

R

QYQRQYY

$$

Sample Output: (Output File: novel.out)

FLBL is a Novel string

FFLL is not a Novel string

ORDINARY is a Novel string

R is a Novel string

QYQRQYY is not a Novel string

Solution:

To attack this problem, you first have to find all the doublets for each distance starting from 0 to the maximum distance which would string's length minus one. Then keep pushing them into a hash set. Whenever the add() method of the Set returns false, it means we are adding a duplicate hence, its not a Novel text. Here is the Java source code.


Cheers!
Braga