CareerCup 150

C.C 1.1

/**
 * 1.1 Implement an algorithm to determine if a string has all unique
 * characters. What if you cannot use additional data structures?
 *
 * @author Jiateng
 */
public class CC1_1 {

    /**
     * sort the characters in the string, then compare from the begin to the end
     * using ASCII
     *
     * @param target
     * @return
     */
    public static int[] aux;

    public static boolean isUnique(String target) {
        int len = target.length();

        int[] asc = new int[len];

        for (int i = 0; i < len; i++) {
            asc[i] = target.charAt(i);
        }

        aux = new int[len];
        sort(asc, 0, len - 1);

        //compare one by one is asc[]
        for (int j = 0; j < len - 1; j++) {
            if (asc[j] == asc[j + 1]) {
                return false;
            }
        }
        return true;
    }

    //divide and conquer
    public static void sort(int[] asc, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        //sort left half
        sort(asc, lo, mid);
        //sort right half
        sort(asc, mid + 1, hi);
        //merge the result
        merge(asc, lo, mid, hi);
    }

    public static void merge(int[] asc, int lo, int mid, int hi) {
        int i = lo;
        int j = mid + 1;
        //copy asc[lo..hi] to aux[lo..hi]
        for (int k = lo; k <= hi; k++) {
            aux[k] = asc[k];
        }

        for (int l = lo; l <= hi; l++) {
            //check if i or j is reached their bound
            if (i > mid) {
                asc[l] = aux[j++];
            } else if (j > hi) {
                asc[l] = aux[i++];
            } //compare the sub array, merge together
            else if (aux[j] < aux[i]) {
                asc[l] = aux[j++];
            } else {
                asc[l] = aux[i++];
            }
        }
    }

    public static void main(String[] args) {

        String target = "absoijsdgsd";

        System.out.println(isUnique(target));
    }
}