找出字符串中无重复最长子串-java实现
时间: 2024-02-23 16:01:49 浏览: 43
可以使用滑动窗口的思想来解决这个问题,具体实现如下:
```java
public static String longestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
String longest = "";
int left = 0, right = 0;
while (right < n) {
char c = s.charAt(right);
if (!set.contains(c)) {
set.add(c);
right++;
if (set.size() > longest.length()) {
longest = s.substring(left, right);
}
} else {
set.remove(s.charAt(left));
left++;
}
}
return longest;
}
```
该方法的时间复杂度为O(n),其中n为字符串s的长度。
相关问题
java中如何找出01串中最长的子串?
可以使用动态规划来解决这个问题,具体步骤如下:
1. 定义状态:用 dp[i] 表示以第 i 个字符结尾的最长的 01 子串的长度。
2. 状态转移方程:如果第 i 个字符是 0,那么 dp[i] = dp[i-1] + 1;如果第 i 个字符是 1,那么 dp[i] = 0。
3. 初始状态:dp[0] = 0。
4. 最终结果:遍历 dp 数组,找到最大值即可。
以下是 Java 代码实现:
public int findMaxSubString(String s) {
int[] dp = new int[s.length()];
dp[0] = 0;
int max = 0;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == '0') {
dp[i] = dp[i-1] + 1;
} else {
dp[i] = 0;
}
max = Math.max(max, dp[i]);
}
return max;
}
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度用java实现
可以使用滑动窗口算法来解决这个问题,具体步骤如下:
1. 定义一个哈希集合用于记录当前窗口中存在的字符。
2. 使用双指针 i 和 j 表示滑动窗口的左右边界,初始值都为 0。
3. 遍历字符串 s,每次移动右指针 j,并将对应的字符加入到哈希集合中。
4. 如果发现哈希集合中已经存在了 s[j] 这个字符,说明当前窗口中存在重复字符,需要移动左指针 i,并将对应的字符从哈希集合中删除,直到窗口中不再存在重复字符为止。
5. 每次移动左指针 i 和右指针 j 后都需要更新最长子串的长度。
下面是 Java 代码实现:
```java
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
if (!set.contains(s.charAt(j))) {
set.add(s.charAt(j++));
ans = Math.max(ans, j - i);
} else {
set.remove(s.charAt(i++));
}
}
return ans;
}
```