Tuesday, January 20, 2015

Mass360 - X-duets

import java.util.HashSet;
import java.util.Set;

/*
 The X-duets of a string of characters are the ordered pairs of characters that  are X distance from each other. A string is X-particular if all its X-duets are different.  A string is Perfect String if it is X-particular for all possible X distances.  For e.g. take the string FLBL, its 0-duets are FL, LB and BL. Since all these are different,  FLBL is 0-particular. Similarly, its 1-duets are FB and LL, since they are different FLBL is  1-particular as well. Lastly, the only 2-duets of FLBL is FL, so FLBL is 2-particular. Hence, FLBL is a Perfect String.

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

Now, take another string FFLL, its 0-duest are FF, FL and LL. Since all these are different,  FFLL is 0-particular. Its 1-duest are FL and FL, since they are same FFLL is not 1-particular.  Hence, FLBL is an imperfect String.

 Write a function called isImperfectString(String input) that returns a Boolean
 Where:
 The "input" is a 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 Perfect string a boolean value
 Sample Input Sample Output
 FLBL         0
 FFLL         1
 ORDINARY 0
 R                 0
 QYQRQYY 1

 */
/**
 * Solution Credit:- http://getinterviewinfo.blogspot.in/2014/07/maas360-ibm-company.html
 */
public class Duets {

    static int isImperfectString(String input) {
        Set set = new HashSet();
        for (int i = 1; i < input.length(); i++) {
            for (int j = 0; j + i < input.length(); j++) {
                String pair = ((char) input.charAt(j) + "" + (char) input.charAt(j + i));
                if (set.contains(pair)) {
                    return 1;
                } else {
                    set.add(pair);
                }
            }
            set.clear();
        }
        return 0;
    }

    public static void main(String[] args) {
        System.out.println(isImperfectString("FLBL"));
        System.out.println(isImperfectString("FFLL"));
        System.out.println(isImperfectString("ORDINARY"));
        System.out.println(isImperfectString("R"));
        System.out.println(isImperfectString("QYQRQYY"));
    }

}