1.最长公共前缀

情况1：比较某一列时，遇到不同字符，i 之前的字符就是解。
情况2：比较某一列时，遇到字符串长度不够，i 之前的字符就是解。
情况3：i 循环自然结束，此时第一个字符串就是解。

package com.dreams.leetcode;

/**
 * 最长公共前缀
 */
public class Leetcode14 {
    static String longestCommonPrefix(String[] strings) {
        char[] first = strings[0].toCharArray(); // 第一个字符串
        for (int i = 0; i < first.length; i++) {
            char ch = first[i];
            for (int j = 1; j < strings.length; j++) {
                // 情况2必须先判断，情况1再判断
                if (strings[j].length() == i || ch != strings[j].charAt(i)) {
                    return new String(first, 0, i);
                }
            }
        }
        return strings[0];
    }

    public static void main(String[] args) {
        System.out.println(longestCommonPrefix(new String[]{"flower", "flow", "flight"})); // fl
    }
}

2.最长回文子串

代码：

package com.dreams.leetcode;

/**
 * 最长回文子串
 */
public class LongestPalindromeLeetcode5 {
    public static void main(String[] args) {
        System.out.println(longestPalindrome("bccbcbabcbafa"));
    }

    static int left; // i
    static int right; // j

    static String longestPalindrome(String s) {
        left = 0;
        right = 0;
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length - 1; i++) {
            extend(chars, i, i); // 一个字符作为中心点
            extend(chars, i, i + 1); // 两个字符作为中心点
        }
        return new String(chars, left, right - left + 1);
    }

    static void extend(char[] chars, int i, int j) {
        while (i >= 0 && j < chars.length
                && chars[i] == chars[j]) { // 如果是回文，扩大回文范围
            i--; // -1
            j++; // 4
        }
        // 退出循环时，i和j指向的不是回文，需要还原
        i++;
        j--;
        if (j - i > right - left) {
            left = i;
            right = j;
        }
    }
}

3.最小覆盖子串

1. 统计目标串需要各种字符个数， 统计原始串 i~j 范围各种字符个数
2. 如果原始串 i~j 范围内不满足条件，j++ 扩大范围，直到满足条件 j 停下来
3. 一旦满足条件 i++ 缩小范围，直到再次不满足条件。
4. 重复 2. 3. 两步直至 j 到达原始串末尾。

代码：

package com.dreams.leetcode;

public class Leetcode76 {
    public static void main(String[] args) {
        System.out.println(minWindow("ADOBECODEBANC", "ABC")); // BANC
    }

    static class Result {
        int i;
        int j;
        public Result(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
    static String minWindow(String s, String t) {
        char[] target = t.toCharArray();
        int[] targetCount = new int[128]; // 目标串字符各出现几次
        for (char ch : target) {
            targetCount[ch]++;
        }
        int passTotal = 0; // 条件总数
        for (int count : targetCount) {
            if (count > 0) {
                passTotal++;
            }
        }
        int passed = 0; // 已通过的条件数

        char[] source = s.toCharArray();
        int[] sourceCount = new int[128]; // 原始串i~j范围内字符各出现几次
        int i = 0;
        int j = 0;
        Result res = null;
        while (j < source.length) {
            // 扩大 j 范围，更新范围内字符计数 和 通过条件数
            char right = source[j];
            sourceCount[right]++;
            if (sourceCount[right] == targetCount[right]) {
                passed++;
            }
            // 若已满足所有条件，缩小 i 范围，更新范围内字符计数 和 通过条件数
            while (passed == passTotal && i <= j) {
                if (res == null) {
                    res = new Result(i, j);
                } else {
                    if (j - i < res.j - res.i) {
                        res = new Result(i, j);
                    }
                }
                char left = source[i];
                sourceCount[left]--;
                if (sourceCount[left] < targetCount[left]) {
                    passed--;
                }
                i++;
            }
            j++;
        }
        return res == null ? "" : new String(source, res.i, res.j - res.i + 1);
    }
}

参考

黑马数据结构