class Solution_DoubleLoop {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() <= 0) {
            return 0;
        }
        int maxCount = 0;
        char[] charArray = s.toCharArray();
        // 外层循环遍历整个字符串
        for (int charIndex = 0; charIndex < charArray.length; charIndex++) {
            int maxSubCount = 0;
            String maxSubStr = "";
            // 内层循环从
            for (int subIndex = charIndex; subIndex < charArray.length; subIndex++) {
                if (maxSubStr.contains("" + charArray[subIndex])) {
                    break;
                } else {
                    maxSubCount++;
                    maxSubStr += charArray[subIndex];
                }
            }
            if (maxSubCount > maxCount) {
                maxCount = maxSubCount;
            }
        }
        return maxCount;
    }
}

class Solution_SlidingWindow_List {
    public int lengthOfLongestSubstring(String s) {
        List<Character> charList = new ArrayList<>();
        int max = 0;
        for (int index = 0; index < s.length(); index++) {
            if (charList.contains(s.charAt(index))) {
                int repeatIndex = charList.indexOf(s.charAt(index));
                for (int rmIndex = 0; rmIndex <= repeatIndex; rmIndex++) {
                    charList.remove(0);
                }
                charList.add(s.charAt(index));
            } else {
                charList.add(s.charAt(index));
                max = Math.max(max, charList.size());
            }
        }
        return max;
    }
}

class Solution_SlidingWindow_Map {
    public int lengthOfLongestSubstring(String s) {
        // 记录遍历过的字符及对应的下标，用于遇到重复字符时，直接移动窗口起始下标到子串重复位的下一位。
        Map<Character, Integer> charMap = new HashMap<>();
        // 表示当前有效子串的起始下标，配合最新字符下标可计算窗口范围（即子串长度）。
        int left = 0;
        // 最大窗口范围（即子串长度）。
        int max = 0;
        for (int index = 0; index < s.length(); index++) {
            char next = s.charAt(index);
            // 只有存在该字符「且记录的位置大于当前窗口起始坐标时」才移动窗口，否则例如 abba：
            //   - 当 index == 2，left = get(b) + 1 = 2，
            //   - 当 index == 3，left = get(a) + 1 = 1，显然不对，此时应该让 left 保持为 2。
            if (charMap.containsKey(next) && charMap.get(next) >= left) {
                left = charMap.get(next) + 1;
            } else {
                max = Math.max(max, (index - left + 1));
            }
            // 不论是否重复都需要记录，如果重复了就需要更新
            charMap.put(next, index);
        }
        return max;
    }
}

class Solution_CenterSpread {
    public String longestPalindrome(String s) {
        // 最长回文子串
        String maxSub = "";
        // 每一轮遍历中当前中心字符的回文子串
        String sub = "";
        // 每一轮遍历中当前中心字符的左侧下标
        int left = 0;
        // 每一轮遍历中当前中心字符的右侧下标
        int right = 0;
        for (int i = 0; i < s.length(); i++) {
            left = i - 1;
            right = i + 1;
            // 最长子串至少也是当前字符
            sub = "" + s.charAt(i);
            // 先向左寻找，与当前字符重复的字符都纳入「中心字符」，直到遇到第一个不重复的为止。
            while (left >= 0 && s.charAt(left) == s.charAt(i)) {
                sub = s.charAt(left) + sub;
                left--;
            }
            // 再向右寻找，与当前字符重复的字符都纳入「中心字符」，直到遇到第一个不重复的为止。
            while (right < s.length() && s.charAt(right) == s.charAt(i)) {
                sub = sub + s.charAt(right);
                right++;
            }
            // 然后同时向两边扩散，如果两侧字符相等，则都纳入子串，直到遇到不相等的一对。
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                sub = s.charAt(left) + sub + s.charAt(right);
                left--;
                right++;
            }
            // 如果当前「中心字符」的回文子串大于记录的最长子串，则更新记录。
            if (sub.length() > maxSub.length()) {
                maxSub = sub;
            }
        }
        return maxSub;
    }
}

class Solution_DynamicProgramming {
    public String longestPalindrome(String s) {
        // 最长回文子串在原字符串的起始下标
        int maxSubLeft = 0;
        // 最长回文子串的长度
        int maxSubLength = 0;
        // 用一个二维数组 dp[left][right] 表示从 s[left]...s[right] 是否为回文子串，
        // dp[left][right] 初始化时默认值全为 false。
        boolean [][] dp = new boolean[s.length()][s.length()];
        // 因为 dp[left][right] 数组的定义，right 一定大于等于 left
        for (int right = 0; right < s.length(); right++) {
            for (int left = 0; left <= right; left++) {
                // 如果 s[left] == s[right]，分为三种情况
                // （1）left == right
                //     表示当前 1 个字符，则肯定是回文子串，dp[left][right] = true
                // （2）right - left = 1
                //     表示 2 个相邻重复字符，既然相等则肯定也是回文子串，dp[left][right] = true
                // （3）right - left > 1
                //     表示子串至少包含 3 个字符，例如 aba 或 abba，则这个子串是否为回文子串，
                //     依赖于 s[left + 1]...s[right - 1] 是否为回文子串，
                //     即依赖于 dp[left + 1][right - 1] 是否为 true。
                // 以上情况（1）和情况（2），都能直接确定 dp[left][right] = true
                if (s.charAt(left) == s.charAt(right)) {
                    if (right - left <= 1) {
                        // 对应情况（1）和情况（2）
                        dp[left][right] = true;
                    } else if (dp[left + 1][right - 1]) {
                        // 对应情况（3）
                        dp[left][right] = true;
                    }
                }
                // dp[left][right] 数组初始化时默认所有元素都是 false，
                // 所以如果 dp[left][right] == true，
                // 就表示上面的条件种判断了 s[left]...s[right] 为回文子串，
                // 则如果这个回文子串的长度大于记录的最大长度，就可以更新记录。
                if (dp[left][right] && right - left + 1 > maxSubLength) {
                    maxSubLeft = left;
                    maxSubLength = right - left + 1;
                }
            }
        }
        // String#substring(startIndex, endIndex) 返回的是一个 [左闭, 右开) 区间
        return s.substring(maxSubLeft, maxSubLeft + maxSubLength);
    }
}

// When: text == regular == empty
matchedLength[0][0] = true,

// When: text == empty, regular[j] == "*"
matchedLength[0][j+1] = matchedLength[0][j-1],

// When: text[i] == regular[j]
matchedLength[i+1][j+1] = matchedLength[i][j],

// When: regular[j] == "*" && text[i] == regular[j - 1]
matchedLength[i+1][j+1] = matchedLength[i][j-1],

// When: regular[j] == "*" && text[i-1] == text[i] == regular[j-1]
matchedLength[i+1][j+1] = matchedLength[i][j+1],

public class RegularExpressMatcher {
    public boolean isMatch(String text, String regular) {
        // 尽管按照题意 text 与 regular 不会为空，但作为代码仍需对边界值保护。
        if (text == null || text.length() <= 0 || regular == null || regular.length() <= 0) {
            return true;
        }
        if (regular.equals(".*")) {
            return true;
        }

        boolean [][]matchedLength = new boolean[text.length() + 1][regular.length() + 1];

        // 0. 已知定义：
        //   - 当 text 与 regular 均为空时，视作匹配；
        matchedLength[0][0] = true;
        //   - 否则仅当 regular 全部由通配体组成时才匹配；
        for (int j = 0; j < regular.length(); j++) {
            if (regular.charAt(j) == '*') {
                matchedLength[0][j + 1] = matchedLength[0][j - 1];
            }
        }

        for (int i = 0; i < text.length(); i++) {
            for (int j = 0; j < regular.length(); j++) {
                if (regular.charAt(j) == '*') {
                    if (isCharMatched(text, i, regular, j - 1)) {
                        // 1. 当遇到通配符、且其前一个字符与文本相同时，则可能匹配零次、一次、多次：
                        //   - 零次："ab" 与 "abb*"，说明可以去掉正则部分
                        //   - 一次："ab" 与 "ab*"，说明可以各自去掉文本与正则部分
                        //   - 多次："abbb" 与 "ab*"，说明可以去掉一个文本部分
                        matchedLength[i + 1][j + 1]
                                = matchedLength[i + 1][j - 1] // 零次
                                || matchedLength[i][j - 1] // 一次
                                || matchedLength[i][j + 1]; // 多次
                    } else {
                        // 2. 当遇到通配符、且前一个字符与文本不同时，则通配体匹配了零次，相当于去掉通配体：
                        matchedLength[i + 1][j + 1] = matchedLength[i + 1][j - 1];
                    }
                } else if (isCharMatched(text, i, regular, j)) {
                    // 3. 当普通字符相同或为 "." 时，则如果各自去掉字符后剩余的匹配，则整串匹配：
                    matchedLength[i + 1][j + 1] = matchedLength[i][j];
                }
            }
        }

        // 最终需要知道的是整串文本（text[0~i]）与整串正则（regular[0~j]）是否匹配，
        // 因此返回的即为 matchedLength[n][m]，其中 n == i+1 == text.length(), m == j+1 == regular.length()。
        return matchedLength[text.length()][regular.length()];
    }

    private boolean isCharMatched(String text, int txtIndex, String regular, int regIndex) {
        if (regular.charAt(regIndex) == '.') {
            return true;
        }
        return (text.charAt(txtIndex) == regular.charAt(regIndex));
    }
}