LongestLinearSubstringer.java

package psamolysov.algo.intro.maxsubarray;

import java.util.LinkedHashMap;
import java.util.Map;

public class LongestLinearSubstringer {

    public static String findLongestKCharSubstring(String str, int k) {
        if (str == null || str.length() < k) {
            return str;
        }
        int longestSubstringBegin = 0, longestSubstringEnd = -1;
        int rightestSubstringBegin = 0, rightestSubstringEnd = -1;
        Map<Character, Integer> uniqueCharPosition = new LinkedHashMap<>(); // insertion order does matter!
        for (int i = 0; i < str.length(); i++) {
            char currentChar = str.charAt(i);
            if (uniqueCharPosition.size() < k || uniqueCharPosition.containsKey(currentChar)) {
                rightestSubstringEnd++;
                // put the current char to the position map
                uniqueCharPosition.put(currentChar, i);
            } else {
                // what is longer?
                if ((rightestSubstringEnd - rightestSubstringBegin) > (longestSubstringEnd - longestSubstringBegin)) {
                    longestSubstringBegin = rightestSubstringBegin;
                    longestSubstringEnd = rightestSubstringEnd;
                }
                // will consider a new rightest substring
                // since we use LinkedHashMap, the leftest unique char (hence the first inserted char)
                // will form the first entry in the map. A new substring will start from
                // the position of this char + 1.
                Map.Entry<Character, Integer> leftmostEntry = null;
                for (Map.Entry<Character, Integer> uniqueEntry : uniqueCharPosition.entrySet()) {
                    leftmostEntry = uniqueEntry;
                    break;
                }
                rightestSubstringBegin = leftmostEntry.getValue() + 1;
                rightestSubstringEnd = i;
                // do not forget to remove the entry from the map: the char is not in the substring more
                uniqueCharPosition.remove(leftmostEntry.getKey());
                // and put the current char to the position map
                uniqueCharPosition.put(currentChar, i);
            }
        }

        // if the longest substring is the rightest one
        if ((rightestSubstringEnd - rightestSubstringBegin) > (longestSubstringEnd - longestSubstringBegin)) {
            longestSubstringBegin = rightestSubstringBegin;
            longestSubstringEnd = rightestSubstringEnd;
        }
        return str.substring(longestSubstringBegin, longestSubstringEnd + 1);
    }

    public static void main(String[] args) {
        System.out.println(findLongestKCharSubstring("O", 1));           // O
        System.out.println(findLongestKCharSubstring("O1", 1));          // O
        System.out.println(findLongestKCharSubstring("paaaveel", 1));    // aaa
        System.out.println(findLongestKCharSubstring("paveel", 1));      // ee
        System.out.println();

        System.out.println(findLongestKCharSubstring("O", 2));                // O
        System.out.println(findLongestKCharSubstring("O1", 2));               // O1
        System.out.println(findLongestKCharSubstring("paval", 2));            // ava
        System.out.println(findLongestKCharSubstring("pavaaal", 2));          // avaaa
        System.out.println(findLongestKCharSubstring("abcababab", 2));        // ababab
        System.out.println(findLongestKCharSubstring("abcababa", 2));         // ababa
        System.out.println(findLongestKCharSubstring("aaaaabbbbbc", 2));      // aaaaabbbbb
        System.out.println(findLongestKCharSubstring("aaaaabbbbbccccc", 2));  // aaaaabbbbb
        System.out.println(findLongestKCharSubstring("aaaaabbbbbcccccc", 2)); // bbbbbcccccc
        System.out.println();

        System.out.println(findLongestKCharSubstring("pav", 3));                   // pav
        System.out.println(findLongestKCharSubstring("paaaall", 3));               // paaaall
        System.out.println(findLongestKCharSubstring("pavaaall", 3));              // avaaall
        System.out.println(findLongestKCharSubstring("abcababa", 3));              // abcababa
        System.out.println(findLongestKCharSubstring("aaaaabbbbbccccc", 3));       // aaaaabbbbbccccc
        System.out.println(findLongestKCharSubstring("aaaaabbbbbcccccxx", 3));     // aaaaabbbbbccccc
        System.out.println(findLongestKCharSubstring("aaaaabbbbbcccccxxxxxx", 3)); // bbbbbcccccxxxxxx
        System.out.println();
    }
}