剑指 Offer 48. 最长不含重复字符的子字符串

题目详情

解法分析

解法一：动态规划+哈希表

package com.walegarrett.offer;

/**
 * @Author WaleGarrett
 * @Date 2021/2/8 20:52
 */

import java.util.HashMap;

/**
 * 题目描述：请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
 */
public class Offer_48 {
    public int lengthOfLongestSubstring(String s) {
        if(s==null || s.length() == 0)
            return 0;
        int len = s.length();
        int[] dp = new int[len];
        HashMap<Character, Integer>map = new HashMap<>();
        dp[0] = 1;
        int result = 1;
        map.put(s.charAt(0), 0);
        for(int j=1;j<len;j++){
            int i = map.getOrDefault(s.charAt(j),-1);
            if(dp[j-1] >= j-i){
                dp[j] = j-i;
            }else{
                dp[j] = dp[j-1] + 1;
            }
            map.put(s.charAt(j), j);
            result = Math.max(result, dp[j]);
        }
        return result;
    }
}

解法二：哈希表+线性遍历

/**
 * 解法二：动态规划+线性遍历
 */
class Offer_48_2 {
    public int lengthOfLongestSubstring(String s) {
        if(s==null || s.length() == 0)
            return 0;
        int len = s.length();
        int[] dp = new int[len];
        HashMap<Character, Integer>map = new HashMap<>();
        dp[0] = 1;
        int result = 1;
        map.put(s.charAt(0), 0);
        for(int j=1;j<len;j++){
            int i = j-1;
            while(i>=0 && s.charAt(i) != s.charAt(j)){
                i--;
            }
            if(dp[j-1] >= j-i){
                dp[j] = j-i;
            }else{
                dp[j] = dp[j-1] + 1;
            }
            result = Math.max(result, dp[j]);
        }
        return result;
    }
}

解法三：双指针+哈希表

/**

 * 解法二：双指针+哈希表
 */
class Offer_48_3 {
    public int lengthOfLongestSubstring(String s) {
        if(s==null || s.length() == 0)
            return 0;
        int len = s.length();
        HashMap<Character, Integer>map = new HashMap<>();
        int result = 1;
        map.put(s.charAt(0), 0);
        int i=-1;
        for(int j=0;j<len;j++){
            if(map.containsKey(s.charAt(j))){
                i= Math.max(i,map.get(s.charAt(j)));
            }
            map.put(s.charAt(j), j);
            result = Math.max(result, j-i);
        }
        return result;
    }
}