lcpBi107

最大字符串配对数目

方法一：记忆化搜索

class Solution {
    public int longestString(int x, int y, int z) {
        dp = new HashMap<>();
        return dfs(x, y, z, ' '); // AA BB AB
    }

    Map<String, Integer> dp;
    private int dfs(int x, int y, int z, char lastChar) {
        if (x == 0 && y == 0 && z == 0)
            return 0;
        String key = x + "," + y + "," + z + "," + lastChar;
        if (dp.containsKey(key))
            return dp.get(key);
        int max = 0;
        if (x > 0 && lastChar != 'A')
            max = Math.max(max, dfs(x - 1, y, z, 'A') + 2);
        if (y > 0 && lastChar != 'B')
            max = Math.max(max, dfs(x, y - 1, z, 'B') + 2);
        if (z > 0 && lastChar != 'A')
            max = Math.max(max, dfs(x, y, z - 1, 'B') + 2);
        dp.put(key, max);
        return max;
    }
}

方法二：记忆化搜索

```



## 字符串连接删减字母

![ ](https://leopold-bucket.oss-cn-guangzhou.aliyuncs.com/img/image-20230704113929490.png)

### 方法一：记忆化搜索

[题解](https://leetcode.cn/problems/decremental-string-concatenation/solutions/1/hui-su-ji-yi-hua-sou-suo-java-by-tailtal-dmix/)

1. 如果当前要合并的单词为words[index]，并且已合并单词str的首尾字符分别为first，last，记words[index]的首尾字符分别为first2, last2。
2. 现在有两种拼接方式：
   1. str + words[index] ：
      - 如果last == first2，那么**拼接成新字符串长度的增量**为len1 = words[index].length() - 1
      - 否则，**拼接成新字符串长度的增量**为len1 = words[index].length()
   2. words[index] + str
      - 如果last2 == first，那么**拼接成新字符串长度的增量**为len2 = words[index].length() - 1
      - 否则，**拼接成新字符串长度的增量**为len2 = words[index].length()
   3. 取min(len1, len2)，存入map中，key为index + ","  + first + "," + last
   4. 在下次遍历到相同index，first，last的时候，**虽然已合并单词str的长度可能不同，但是字符串长度增量是相同的！**

```java
class Solution {
    public int minimizeConcatenatedLength(String[] words) {
        this.words = words;
        n = words.length;
        dp = new HashMap<>();
        int res = dfs(1, words[0].charAt(0), words[0].charAt(words[0].length() - 1)) + words[0].length();
        return res;
    }

    String[] words;
    int n;
    Map<String, Integer> dp;

    private int dfs(int index, char first, char last) {
        if (index == n)
            return 0;
        String key = index + ","  + first + "," + last;
        if (dp.containsKey(key))
            return dp.get(key);
        char first2 = words[index].charAt(0), last2 = words[index].charAt(words[index].length() - 1);
        int min = Integer.MAX_VALUE;
        // first插入到words[index]后面
        int res1 = dfs(index + 1, first2, last);
        min = Math.min(min, res1 + words[index].length() - (first == last2 ? 1 : 0));
        // last插入到words[index]前面
        int res2 = dfs(index + 1, first, last2);
        min = Math.min(min, res2 + words[index].length() - (last == first2 ? 1 : 0));
        dp.put(key, min);
        return min;
    }
}

统计没有收到请求的服务器数目

方法一：模拟(超时)

class Solution {
    public int[] countServers(int n, int[][] logs, int x, int[] queries) {
        int[] res = new int[queries.length];
        int maxTime = 0;
        for (int q : queries)
            maxTime = Math.max(maxTime, q);
        int[][] arr = new int[n + 1][(int) 1e6];
        for (int[] log : logs) {
            arr[log[0]][log[1]] = 1;
        }
        for (int k = 0; k < queries.length; ++k) {
            int right = queries[k], left = right - x;
            for (int i = 1; i <= n; ++i) {
                boolean flag = false;
                for (int j = left; j <= right; ++j) {
                    if (arr[i][j] == 1) {
                        flag = true;
                        break;
                    }
                }
                if (!flag)
                    ++res[k];
            }
        }
        return res;
    }
}