14：字符串中的变位词

:::info 题目：输入字符串s1和s2，如何判断字符串s2中是否包含字符串s1的某个变位词？如果字符串s2中包含字符串s1的某个变位词，则字符串s1至少有一个变位词是字符串s2的子字符串。假设两个字符串中只包含英文小写字母。例如，字符串s1为”ac”，字符串s2为”dgcaf”，由于字符串s2中包含字符串s1的变位词”ca”，因此输出为true。如果字符串s1为”ab”，字符串s2为”dgcaf”，则输出为false。 :::

public class CheckInclusion {
    public static boolean checkInclusion(String s1, String s2) {
        if (s2.length() < s1.length()) {
            return false;
        }
        int[] countTable = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            // 先统计s1中字符的数量
            countTable[s1.charAt(i) - 'a']++;
            // 借这个循环同时统计s2的前s1.length()的字符
            countTable[s2.charAt(i) - 'a']--;
        }
        if (checkAllZero(countTable)) {
            return true;
        }
        // 双指针走s2的后半段
        for (int i = s1.length(); i < s2.length(); i++) {
            // 右指针挪一位，相当于纳入当前的子字符串的统计范围，减去1
            countTable[s2.charAt(i) - 'a']--;
            // 左指针挪一位，相当于被剔除当前的字符串的统计范围，加回1
            countTable[s2.charAt(i - s1.length()) - 'a']++;
            if (checkAllZero(countTable)) {
                return true;
            }
        }
        return false;
    }
    private static boolean checkAllZero(int[] countTable) {
        for (int count : countTable) {
            if (count != 0) {
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        System.out.println(checkInclusion("ac", "bcade"));
        System.out.println(checkInclusion("ec", "bcade"));
    }
}

16：不含重复字符的最长子字符串

:::info 题目：输入一个字符串，求该字符串中不含重复字符的最长子字符串的长度。例如，输入字符串”babcca”，其最长的不含重复字符的子字符串是”abc”，长度为3。 :::

public class CheckLongestSubString16 {
    public static int findLongestSubString(String str) {
        if (str.length() == 0) {
            return 0;
        }
        int maxLength = 1;
        // 辅助数组来统计当前字符串中个是否有重复数字
        int[] countTable = new int[256];
        // 辅助标记，记录当前子字符串中，重复字母的个数
        int duplicateNum = 0;
        int left = -1;
        int right = 0;
        for (; right < str.length(); right++) {
            // 右指针代表子数组的右侧最后一个字符，记录当前字符的出现次数
            countTable[str.charAt(right)]++;
            if (countTable[str.charAt(right)] == 2) {
                duplicateNum++;
            }
            while (duplicateNum > 0) {
                // 如果有重复的字符，则移动左指针，直到没有重复字符为止
                left++;
                countTable[str.charAt(left)]--;
                if (countTable[str.charAt(left)] == 1) {
                    duplicateNum--;
                }
            }
            maxLength = Math.max(maxLength, right - left);
        }
        return maxLength;
    }
    public static void main(String[] args) {
        System.out.println(findLongestSubString("babcca"));
    }
}

字符可以隐式转换为数字，作为数组的下标在Java中，char 类型的字符可以隐式转换为对应的整数值，基于其在Unicode字符集中的编码。因为Unicode是ASCII的超集，ASCII值范围内的字符（即0到127）的Unicode编码与ASCII码相同。因此，在需要整数类型时，字符会自动转换为其相应的ASCII（或Unicode）码。
这就是为什么您可以直接在需要整数的上下文中使用字符，比如用作数组的索引。例如：

1char character = 'A'; // 'A' 在ASCII中的值是 65
2int asciiValue = character; // 字符 'A' 自动转换成整数 65
3int[] array = new int[128]; // 数组大到足以包含所有ASCII字符
4array[character] = 10; // 使用字符 'A' 作为索引赋值，等同于 array[65] = 10;

在上述代码中，character 变量是一个char类型，存储了字符 ‘A’。当将character赋值给整数变量asciiValue时，字符 ‘A’ 会自动转换为其ASCII值，也就是65。同样地，当将character用作数组array的索引时，它会被隐式转换为整数65，即数组的第66个元素（因为数组索引从0开始）。
需要注意的是，这种隐式转换是单向的，即可以将char隐式转换为int，但将int转换为char需要显式的类型转换：

1int number = 65;
2char convertedChar = (char) number; // 显式地将整数65转换为字符 'A'

在显式转换的情况下，您需要使用类型转换操作符(char)来指明您想要将整数转换为字符。

17：包含所有字符的最短字符串

:::info 题目：输入两个字符串s和t，请找出字符串s中包含字符串t的所有字符的最短子字符串。例如，输入的字符串s为”ADDBANCAD”，字符串t为”ABC”，则字符串s中包含字符’A’、’B’和’C’的最短子字符串是”BANC”。如果不存在符合条件的子字符串，则返回空字符串””。如果存在多个符合条件的子字符串，则返回任意一个。 :::

public class minWindow17 {
    public static String minWindow(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        Map<Character, Integer> countTable = new HashMap<>();
        // 先统计t中所有字符的数量
        for (int i = 0; i < t.length(); i++) {
            countTable.put(t.charAt(i), countTable.getOrDefault(t.charAt(i), 0) + 1);
        }
        // 用来标记是否t中所有的字符包含了
        int countFlag = countTable.size();
        int minLength = Integer.MAX_VALUE;
        int minStart = 0;
        int minEnd = 0;
        // 然后双指针遍历s
        int left = 0;
        int right = 0;
        // 循环继续的条件
        // 条件1数组还没走完
        // 条件2数组走完了，也找到最小数组了，此时还可以移动左指针，找更小的数组
        while (right < s.length() || (countFlag == 0 && right == s.length())) {
            if (countFlag > 0) {
                // 还没找到包含t的数组，那就要移动右指针，同时确认新增的字符是否在t中
                char c = s.charAt(right);
                if (countTable.containsKey(c)) {
                    // 如果有那就要减掉
                    countTable.put(c, countTable.get(c) - 1);
                    if (countTable.get(c) == 0) {
                        // 如果当前字符全剪完了，要从flag中减掉
                        countFlag--;
                    }
                }
                right++;
            } else {
                // 如果count=0，就意味着当前left 到 right 中间的子数组已经包含了t
                // 此时要做两件事情：第一，判断当前子数组长度是否比之前的小
                if (right - left < minLength) {
                    minLength = right - left;
                    minStart = left;
                    minEnd = right;
                }
                // 第二，尝试右移左指针，来看是否可能有更短的
                char c = s.charAt(left);
                if (countTable.containsKey(c)) {
                    // 如果有那就要加回去
                    countTable.put(c, countTable.get(c) + 1);
                    if (countTable.get(c) == 1) {
                        countFlag++;
                    }
                }
                left++;
            }
        }
        return minLength == Integer.MAX_VALUE ? "" : s.substring(minStart, minEnd);
    }
    public static void main(String[] args) {
        String s = "asdfabcd";
        String t = "abd";
        System.out.println(minWindow(s, t));
    }
}

18：有效的回文

:::info 题目：给定一个字符串，请判断它是不是回文。假设只需要考虑字母和数字字符，并忽略大小写。例如，”Was it a cat I saw？”是一个回文字符串，而”race a car”不是回文字符串。 :::

public static boolean isPalindrome(String s) {
    int left = 0;
    int right = s.length() -1;
    while (left < right) {
        char leftChar = s.charAt(left);
        char rightChar = s.charAt(right);
        // 忽略除字符或者数字之外的其他字符
        if (!Character.isLetterOrDigit(leftChar)) {
            left++;
        } else if (!Character.isLetterOrDigit(rightChar)) {
            rightChar--;
        } else {
            // 左右比较
            char l = Character.toLowerCase(leftChar);
            char r = Character.toLowerCase(rightChar);
            if (l != r) {
                return false;
            }
            // 如果比较通过，则将两边的指针分别相向移动
            left++;
            right--;
        }
    }
    return true;
}

19：最多删除一个字符得到回文

:::info 题目：给定一个字符串，请判断如果最多从字符串中删除一个字符能不能得到一个回文字符串。例如，如果输入字符串”abca”，由于删除字符’b’或’c’就能得到一个回文字符串，因此输出为true。 :::

public class Palindrome19 {
    public static boolean isPalindrome(String str) {
        int left = 0;
        int right = str.length() - 1;
        // 第一次回文判断，允许有部队称发生
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                break;
            }
            left++;
            right--;
        }
        if (left == right) {
            // 如果第一次就校验通过了，直接返回
            return true;
        } else {
            // 跳过左侧字符，或者右侧字符，只要有一个是回文就可以了
            return checkPalindrome(str, left + 1, right) || checkPalindrome(str, left, right + 1);
        }
    }
    public static boolean checkPalindrome(String str, int left, int right) {
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
    public static void main(String[] args) {
        System.out.println(isPalindrome("qw1eewq"));
        System.out.println(isPalindrome("qw11eewq"));
        System.out.println(isPalindrome("qw1eew1q"));
    }
}

20：回文子字符串的个数

:::info 题目：给定一个字符串，请问该字符串中有多少个回文连续子字符串？例如，字符串”abc”有3个回文子字符串，分别为”a”、”b”和”c”；而字符串”aaa”有6个回文子字符串，分别为”a”、”a”、”a”、”aa”、”aa”和”aaa”。 :::

/**
 * @author jiaming
 * @version CountPalindrome20.java, v 0.1 2024年02月06日 19:16 jiaming
 */
public class CountPalindrome {
    public static int countPalindrome(String str) {
        int count = 0;
        int centerIndex=0;
        for( ; centerIndex < str.length(); centerIndex++) {
            count += countPalindromeFromCenter(str, centerIndex, centerIndex);
            count += countPalindromeFromCenter(str, centerIndex, centerIndex+1);
        }
        return count;
    }
    private static int countPalindromeFromCenter(String str, int left , int right) {
        int count = 0;
        while(left >= 0 && right < str.length()) {
            if(str.charAt(left) == str.charAt(right)) {
                count++;
                left--;
                right++;
            } else {
                break;
            }
        }
        return count;
    }
    public static void main(String[] args) {
        System.out.println(countPalindrome("aaa"));
    }
}