leetcode-go/written-exam/freewheel-onsite-2019/no2/Main.java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        for (String str : split("")) {
            System.out.printf("%s\t", str);
        }
        System.out.println();
        for (String str : split(null)) {
            System.out.printf("%s\t", str);
        }
        System.out.println();
        for (String str : split("abc")) {
            System.out.printf("%s\t", str);
        }
        System.out.println();
        for (String str : split("abecadefgfg")) {
            System.out.printf("%s\t", str);
        }
        System.out.println();
    }

    public static String[] split(String input) {
        if (input == null) return new String[] {};
        if (input.length() <= 1) return new String[] {input};
        char[] chars = input.toCharArray();
        int[] last = new int[256];
        for (int i = 0; i < chars.length; i++) {
            char ch = chars[i];
            last[ch] = Math.max(last[ch], i);
        }
        int prev = 0;
        int next = last[chars[0]];
        List<String> list = new ArrayList<>();
        for (int i = 0; i < chars.length; i++) {
            char ch = chars[i];
            if (i == next) {
                list.add(input.substring(prev, i + 1));
                prev = i + 1;
                next = i == chars.length - 1 ? chars.length : last[chars[i + 1]];
            } else {
                next = Math.max(next, last[ch]);
            }
        }
        String[] strs = new String[list.size()];
        list.toArray(strs);
        return strs;
    }
}