华为机试1——最长子串_求满足条件的最长子串的长度

华为机试1——最长子串

题目描述：

给定一个字符串String，求取该字符串满足条件的最长子串的长度。
条件：该子串中各字符最多出现两次。

---

测试用例：

输入：abcabcbb
输出：6

说明：子串abcabc每个字符出现的次数都小于等于2，满足条件且为最长，输出长度6。

---

机试时答题情况：

import java.util.Scanner;
import java.lang.Math;
import java.util.HashMap;

public class Main{
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        
        int max=0;
        for(int j=0;j<str.length();j++){
            HashMap<Character, Integer> map = new HashMap<Character,Integer>();
            String sub = str.substring(j);
            for(int i=0;i<sub.length();i++){
                if(!map.containsKey(sub.charAt(i))){
                    map.put(sub.charAt(i),1);
                }
                else{
                    int time = map.get(sub.charAt(i));
                    if(time<2){
                        time++;
                        map.put(sub.charAt(i),time);
                    }
                    else{
                        max = Math.max(max,i);
                        break;
                    }
                }
            }
        }
        System.out.println(max);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

该题的思路基本上是属于暴力破解，每次循环往后移动一位，判断以i为开头的字符串的最大子串长度，用线性探测的方法向后探测，用一个HashMap记录每个字符出现的个数，即key值记录字符，value值记录该字符出现的次数。循环中进行判断：

• 如果hashmap中没有该字符，则加入该字符并记录value值为1；
• 如果有该字符则判断该字符的个数：
  • 如果小于2则value值加一；
  • 如果大于等于2则说明该字符已出现第3次，退出本轮循环，并用当前的子串长度与max子串长度作比较，选取最大值。

该思路的时间复杂度为O(n${}^2$)，空间复杂度为每轮都要新建一个HashMap；

该做法自测时能通过上面那个测试用例，但提交后只能通过30%的测试用例。

---

优化后思路

先说一下我上面这个做法最大的错误，在上面的这个代码中，如果给定的字符串一个重复字符都没有或者相同字符只出现2次及以下的话，我最终的结果会输出0

原因是因为指针一直后移，一直没有更新max的值，导致循环结束后max仍然为0；
低级错误啊！!

下面开始优化后的思路：
优化前，每轮循环都需要构建一个新的HashMap；优化后，只需要一个HashMap即可；
优化后时间复杂度大大降低；

先说思路：还是向后线性探测的基础思路，我们在上面未优化的思路中发现，其实每次往后移一位就构建HashMap过于冗余，实际上真正构成本轮结束的就只是最后的那一个字符。因此，我们想到用双指针的方法：

1. i 用于记录开头的位置，j 向后探测
   • 当该字符在HashMap中没有时，则添加；
   • 当该字符在HashMap中次数为1时，加一；
2. 当该字符出现第3次时开始处理：
   • 记录当前的子串的距离，即为 j-i ，与最大值进行比较，更新最大子串长度；
   • 将 i 的值向后遇到的每一个字符都在HashMap中减一，直到 i 走到 和 j 相等的那个值的后一个；（因为就是 j 的这个值导致的子串探测结束，那么我们就将第一个遇到的 j 的值跳过）
3. 重复，直到 j 遍历完整个字符串；

记得循环结束的时候再判断一次 j-i 的值是否大于max的值；

import java.util.Scanner;
import java.lang.Math;
import java.util.HashMap;

public class Main{
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        
        int max=0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int i=0;
        int j=0;
        for(j=0;j<str.length();j++){
        	//hashmap中不含当前元素，则添加并记录1
            if(!map.containsKey(str.charAt(j))) {
            	map.put(str.charAt(j), 1);
            	continue;
            }
            
            int times = map.get(str.charAt(j));
            //次数此时出现2次
            if(times<2)
            	map.put(str.charAt(j), times+1);
            //次数此时出现第3次
            else {
            	max = Math.max(max, j-i);
            	while(str.charAt(i) != str.charAt(j)) {
            		int time = map.get(str.charAt(i));
            		map.put(str.charAt(i), time-1);
            		i++;
            	}
            	map.put(str.charAt(i), times-1);
            	i++;
            }
        }
        max = Math.max(max, j-i);
        
        System.out.println(max);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

由于没有测试用例了，无法验证正确性，从理论上看应该没啥问题。

力扣中类似的题目：

剑指 Offer 48. 最长不含重复字符的子字符串
至多包含两个不同字符的最长子串（滑动窗口）