1、 Longest substring without repeating characters

3. Longest substring without repeating characters
Slide the window to solve the problem . Set up a map To store characters and where they appear , Redefine the start and end pointer of the window .

public static int lengthOfLongestSubstring(String s) {
    // Boundary check 
    if (s == null || s.isEmpty()) {
        return 0;
    }
    // result 
    int res = 0;
    // Define a map,key Store characters that don't repeat ,val For the position of the character 
    Map<Character, Integer> map = new HashMap<>();
    for (int start = 0, end = 0; end < s.length(); end++) {
        char c = s.charAt(end);
        if (map.containsKey(c)) {
            start = Math.max(map.get(c), start);
        }
        res = Math.max(end - start + 1, res);
        map.put(c, end + 1);
    }
    return res;
}

2、 Longest common subsequence

1143. Longest common subsequence
It involves the problem of finding subsequences of two strings , Generally, it is the category of dynamic programming . The difficulty is to find the state transition equation .
Define a two-dimensional array dp The length used to store the longest common subsequence , among dp[i][j] Express S1 Before i Characters and S2 Before j The length of the longest common subsequence of characters . consider S1i And S2j Whether the values are equal , It can be divided into the following two situations :
Refer to this ！！

  public static int longestCommonSubsequence(String text1, String text2) {
    // Boundary check 
    if (text1 == null || text1.isEmpty()) {
        return 0;
    }
    if (text2 == null || text2.isEmpty()) {
        return 0;
    }
    int n1 = text1.length(), n2 = text2.length();
    int[][] dp = new int[n1 + 1][n2 + 1];
    // State transition equation 
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }
    return dp[n1][n2];
}

3、 Longest repeating subarray

718. Longest repeating subarray
Dynamic programming problem ：

public static int findLength(int[] A, int[] B) {
    // Boundary check 
    if (A.length <= 0 || B.length <= 0) {
        return 0;
    }
    int result = 0;
    int n = A.length;
    int m = B.length;
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (A[i - 1] == B[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                result = Math.max(result, dp[i][j]);
            }
        }
    }
    return result;
}

4、 String inversion

Using two Pointers .

public static void reverseString(char[] s) {
    // Boundary check 
    if (s.length <= 1) {
        return;
    }
    // Double finger needling 
    int left = 0, right = s.length - 1;
    while (left < right) {
        char tmp = s[left];
        s[left++] = s[right];
        s[right--] = tmp;
    }
}

5、 Can a string consist of words in a dictionary

Given a string s And a dictionary dict, Determine whether a string can be composed of strings in a dictionary , A string in a dictionary can appear more than once . for example s=“Ilovebytedance”,dict={“I”,“love”,“bytedance”}
With dynamic programming ,dp[i] Representation string s[0~i] Whether it is separable bool value .
Bytes to beat Word splicing
139. Word splitting
Reference resources here ！！！
It's also a dynamic programming problem ：

 public static boolean wordBreak(String s, List<String> wordDict) {
    Set<String> wordDictSet = new HashSet(wordDict);
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.length()];
}

6、 A full permutation of a given string

Algorithm problem solution ： Given a string, output all strings in its full permutation form （JAVA Code ）
The full permutation of strings Java Realization
The idea of recursion and backtracking .

summary

Most of the common string algorithms are dynamic programming problems .