1. Longest substring without repeated characters (stress deduction 3)
Given a string s, please find the length of the longest substring that does not contain duplicate characters.
Example 1:
input: s = "abcabcbb" output: 3 explain: Because the longest substring without duplicate characters is "abc"，So its length is 3.
You can use "sliding window" to solve this problem:
- We use two pointers to represent the left and right boundaries of a substring (or window) in the string. The left pointer represents the left boundary of the window "the starting position of the enumeration substring", and the right pointer represents the right boundary of the window
In each step of operation, we will move the left pointer to the right by one grid, indicating that we start enumerating the next character as the starting position, and then we can constantly move the right pointer to the right, but we need to ensure that there are no duplicate characters in the substring corresponding to the two pointers. After the movement, this substring corresponds to the longest substring that starts with the left pointer and does not contain duplicate characters. We record the length of this substring;
The length of the substring we find is the longest after enumeration. - Judge repeated characters:
In the above process, we also need to use a data structure to judge whether there are duplicate characters. The commonly used data structure is hash set (i.e. HashSet in Java). When the left pointer moves to the right, we remove a character from the hash set, and when the right pointer moves to the right, we add a character to the hash set.
Author: LeetCode-Solution Link: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/ Source: force buckle( LeetCode)
//Longest unrepeated character substring
public static int longestNoRepeatSubstring(String str){
int len = str.length();
Set<Character> set = new HashSet<>();
int slidePtr = 0;
int maxLen = 0;
for(int i = 0; i < len; i++){
while(slidePtr < len && !set.contains(str.charAt(slidePtr))){
set.add(str.charAt(slidePtr));
slidePtr++;
}
maxLen = Math.max(maxLen, slidePtr-i);
set.remove(str.charAt(i));
}
return maxLen;
}
2. Longest common subsequence (corresponding stress deduction 1143)
Given two strings text1 and text2, returns the length of the longest common subsequence of the two strings. If there is no common subsequence, 0 is returned
The subsequence of a string refers to such a new string: it is a new string composed of the original string after deleting some characters (or not deleting any characters) without changing the relative order of characters.
- For example, "ace" is a subsequence of "abcde", but "aec" is not a subsequence of "abcde".
The common subsequence of two strings is the subsequence shared by the two strings. - Example 1:
Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: the longest common subsequence is "ace" ，Its length is 3.
Problem solving ideas
The problem of finding the longest common subsequence of two arrays or strings must use dynamic programming
Firstly, two concepts are distinguished: subsequences can be discontinuous; Subarray (substring) needs to be continuous;
In addition, dynamic programming also has a routine: when dynamic programming is used for a single array or string, dynamic programming dp[i] can be defined as the result required in num [0: I]; When two arrays or strings need dynamic programming, dynamic programming can be defined as two-dimensional dp[i][j], which means the desired result obtained by matching between A[0:i] and B[0:j].
-
State definition
For example, for this question, dp[i][j] can be defined to represent the longest common subsequence of text1[0:i-1] and text2[0:j-1]. (Note: text1[0:i-1] refers to the 0th element to the i-1st element of text1, which are included at both ends)
The reason why dp[i][j] is not defined as text1[0:i] and text2[0:j] is to facilitate the matching between an empty string and another string when i = 0 or j = 0, so that dp[i][j] can be initialized to 0 -
State transition equation
After knowing the state definition, we begin to write the state transition equation.
When text1[i - 1] == text2[j - 1], the last bit of the two substrings is equal, so the longest common subsequence is increased by 1, so dp[i][j] = dp[i - 1][j - 1] + 1; For example, for ac and bc, the length of their longest common subsequence is equal to the length of the longest common subsequence of a and b, 0 + 1 = 1.
When text1 [I - 1]= Text2 [J - 1], indicating that the last bit of the two substrings is not equal, then the state dp[i][j] at this time should be the maximum value of dp[i - 1][j] and dp[i][j - 1]. For example, for ACE and bc, the length of their longest common subsequence is equal to the maximum of ① ace and b's longest common subsequence length 0 and ② ac and bc's longest common subsequence length 1, = 1.
To sum up, the state transition equation is:
d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + 1 , When t e x t 1 [ i − 1 ] = = t e x t 2 [ j − 1 ] ; dp[i][j] = dp[i - 1][j - 1] + 1, when text1[i - 1] == text2[j - 1]; dp[i][j]=dp[i − 1][j − 1] + 1, when text1[i − 1]==text2[j − 1];d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) , When t e x t 1 [ i − 1 ] ! = t e x t 2 [ j − 1 ] dp[i][j]=max(dp[i − 1][j],dp[i][j − 1]), when text1 [I - 1]= text2[j - 1] dp[i][j]=max(dp[i − 1][j],dp[i][j − 1]), when text1[i − 1]= text2[j−1]
-
Initialization of state
Initialization depends on the value of dp[i][j] when i = 0 and j = 0.When i = 0, dp[0][j] represents the longest common subsequence of empty string and text2 in text1, and the result must be 0
When j = 0, dp[i][0] represents the longest common subsequence of empty string and text1 in text2, and the result must be 0
To sum up, when i = 0 or j = 0, dp[i][j] is initialized to 0 -
Traversal direction and range
Because dp[i][j] depends on DP [I - 1] [J - 1], DP [I - 1] [J], dp[i][j - 1], the traversal order of I and j must be from small to large.
In addition, when I and j are 0, dp[i][j] = 0, and the initialization of dp array itself is 0. Therefore, let I and j traverse directly from 1. The end of the traversal should be the length of the string len(text1) and len(text2). -
Final return result
Because dp[i][j] means the longest common subsequence of text1[0:i-1] and text2[0:j-1]. We finally hope to find the longest common subsequence of text1 and text2. Therefore, the result to be returned is dp[len(text1)][len(text2)] when i = len(text1) and j = len(text2).
Author: fuxuemingzhu Link: https://leetcode-cn.com/problems/longest-common-subsequence/solution/fu-xue-ming-zhu-er-wei-dong-tai-gui-hua-r5ez6/ Source: force buckle( LeetCode)
//Longest common subsequence
public static int longestCommonSequence(String str1, String str2){
int len1 = str1.length();
int len2 = str2.length();
int[][] dp = new int[len1+1][len2+1];
dp[0][0] = 0; //If the lengths of Str1 and str2 are both 0, the length of the common substring is also 0
for(int i = 1; i < len1+1; i++){
for(int j = 1; j < len2+1; j++){
if(str1.charAt(i-1) == str2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] + 1;
}else{
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[len1][len2];
}*/
3. Longest common substring
The idea and solution are basically consistent with the longest common subsequence
The equation of state is:
d
p
[
i
]
[
j
]
=
d
p
[
i
−
1
]
[
j
−
1
]
+
1
,
When
t
e
x
t
1
[
i
−
1
]
=
=
t
e
x
t
2
[
j
−
1
]
;
dp[i][j] = dp[i - 1][j - 1] + 1, when text1[i - 1] == text2[j - 1];
dp[i][j]=dp[i − 1][j − 1] + 1, when text1[i − 1]==text2[j − 1];
d p [ i ] [ j ] = 0 , When t e x t 1 [ i − 1 ] ! = t e x t 2 [ j − 1 ] dp[i][j]=0, when text1 [I - 1]= text2[j - 1] dp[i][j]=0, when text1[i − 1]= text2[j−1]
//Longest common substring
public static int longestCommonString(String str1, String str2){
int len1 = str1.length(), len2 = str2.length();
int[][] dp = new int[len1+1][len2+1];
int maxLen = 0;
int endIndexOfStr1 = 0;
dp[0][0] = 0;
for(int i = 1; i < len1; i++){
for(int j = 1; j <len2; j++){
if(str1.charAt(i-1) == str2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] + 1;
if(maxLen < dp[i][j]){
maxLen = dp[i][j];
endIndexOfStr1 = i;
}
}//else
//dp[i][j] = 0;
//}
}
}
//return str1.substring(endIndexOfStr1-maxLen, endIndexOfStr1);
return maxLen;
}*/
4. Code sorting
import java.util.*;
class Solution {
public static void main(String[] args) {
String str = "abcdecghij";
String s1 = "abcdefhjas";
String s2 = "deabcdejsfhmmn";
System.out.println(longestNoRepeatSubstring(str)); //result: 7,decghij
//System.out.println(longestCommonSequence(s1, s2)); //result: 7, abcdejs
//System.out.println(longestCommonString(s1, s2)); //result: 5, abcde
}
//Longest unrepeated character substring
public static int longestNoRepeatSubstring(String str){
int len = str.length();
Set<Character> set = new HashSet<>();
int slidePtr = 0;
int maxLen = 0;
for(int i = 0; i < len; i++){
while(slidePtr < len && !set.contains(str.charAt(slidePtr))){
set.add(str.charAt(slidePtr));
slidePtr++;
}
maxLen = Math.max(maxLen, slidePtr-i);
set.remove(str.charAt(i));
}
return maxLen;
}
/*
//Longest common substring
public static int longestCommonString(String str1, String str2){
int len1 = str1.length(), len2 = str2.length();
int[][] dp = new int[len1+1][len2+1];
int maxLen = 0;
int endIndexOfStr1 = 0;
dp[0][0] = 0;
for(int i = 1; i < len1; i++){
for(int j = 1; j <len2; j++){
if(str1.charAt(i-1) == str2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] + 1;
if(maxLen < dp[i][j]){
maxLen = dp[i][j];
endIndexOfStr1 = i;
}
}//else
//dp[i][j] = 0;
//}
}
}
//return str1.substring(endIndexOfStr1-maxLen, endIndexOfStr1);
return maxLen;
}*/
/*
//Longest common subsequence
public static int longestCommonSequence(String str1, String str2){
int len1 = str1.length();
int len2 = str2.length();
int[][] dp = new int[len1+1][len2+1];
dp[0][0] = 0; //Str1 If the lengths of str2 and str2 are both 0, the length of the common substring is also 0
for(int i = 1; i < len1+1; i++){
for(int j = 1; j < len2+1; j++){
if(str1.charAt(i-1) == str2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] + 1;
}else{
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[len1][len2];
}*/
}