Monday, January 16, 2012

Print continuous longest substring without repeting chars from a charcter array

Longest consecutive substring without repetition


To find the longest substring without repetition of characters from an array of characters.
Let's suppose the string is "helloforhellowhy"
There are 1 continuous substring, with maximum length, without char repetition
"forhel" -- length =6

Another Example String: "nevertheless"  
 Maximum length without repetition: "verth" -- length = 5

String : aback
output: back -- length = 4

Belwo program prints the first string. It can be modified a bit to print all the possible substrings with maximum length



--------------------------------------------------------------------------------------

public class LongestSubstring {

    public static int[] longestWithoutRepeat(char[] input) {
        if (input == null || input.length == 0)
            return null;
        HashMap map = new HashMap<>(input.length);

        int[] lastIndices = new int[] { 0, 0 };
        int[] currentIndices = new int[] { 0, 0 };
        map.put(Character.valueOf(input[0]), 0);

        int j = input.length;
        int i = 1;

        while (i < j) {
            char c = input[i];
            Integer matchingCharIndex = null;

            if ((matchingCharIndex = map.get(Character.valueOf(c))) != null) {
                map.clear();
                updateLastIndices(lastIndices, currentIndices);
                currentIndices[0] = currentIndices[1] = matchingCharIndex.intValue() + 1;
                i = currentIndices[1];
                continue;
            }
            map.put(Character.valueOf(c), i);
            currentIndices[1] = i++;
        }
        updateLastIndices(lastIndices, currentIndices);
        return lastIndices;
    }

    private static int[] updateLastIndices(int[] lastIndices,
            int[] currentIndices) {
        if ((currentIndices[1] - currentIndices[0]) > (lastIndices[1] - lastIndices[0])) {
            lastIndices[1] = currentIndices[1];
            lastIndices[0] = currentIndices[0];
        }
        return lastIndices;
    }

    private static void print(char[] input, int[] lastIndices) {
        System.out.println("Greatest len = "
                + (lastIndices[1] - lastIndices[0] + 1));
        for (int m = lastIndices[0]; m <= lastIndices[1]; m++) {
            System.out.print(input[m]);
        }
    }

    public static void main(String[] args) {

        String test = "helloforhellowhy"; // forhel, 6 passed
        String test0 = "hellofaorhellowhyasmn"; // lowhyasmn 9, passed
        String test1 = "neverthaless"; // verthal 7, passed
        String test2 = "eee"; // e, paseed
        String test3 = "heeeeiop"; // eiop, passed
        String test4 = "343jbb6n78opnei"; // b6n78op7
        String test5 = "abcabcde";
        String test6 = "aback";
        String test7 = "hellofa";
        String test8 = "abcdefcghfa"; // abcdef 6
        String test9 = "abadbg";
        String test10 = "abakk";
       
        String input = test10;
        System.out.println("Input array = " + input + " ,Length="
                + input.length());
        int[] lastIndices = longestWithoutRepeat(input.toCharArray());

        print(input.toCharArray(), lastIndices);
    }
}

No comments:

Post a Comment