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

## No comments:

Post a Comment