字符串求最长不重复子串

题目

leetcode原题，返回子串的长度的

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

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] ch = s.toCharArray();
        int n = ch.length;
        if(n == 0)return 0;
        // 存放以字符string.charAt(i)结尾的最长子字符串的长度
        int[] dp = new int[n];
        dp[0] = 1;
        // map存放字符在字符串中的位置
        HashMap<Character,Integer> map = new HashMap<>();
        map.put(ch[0],0);
        int len = 1;
        for(int i = 1; i < n; i++){
            if(map.containsKey(ch[i])){
                int idx = map.get(ch[i]);
                dp[i] = Math.min(i - idx,dp[i - 1] + 1);
            }else{
                dp[i] = dp[i - 1] + 1;
            }
            // 不管重复不重复都要存最新的位置
            map.put(ch[i],i);
            len = Math.max(len,dp[i]);
        }
        return len;
    }
}

如果换成返回字符串？

给你一个字符串，要求返回最长的子串，子串中字符不能重复。

只需稍微做些修改~

leetcode上是返回子串的长度，题目是要返回子串。

import java.util.*;

public class MaxString {
    public static void main(String[] args) {
        lengthOfLongestSubstring("abcabcbb");
    }
    public static void lengthOfLongestSubstring(String s) {
        char[] ch = s.toCharArray();
        int n = ch.length;
        if(n == 0)return;
        // 存放以字符string.charAt(i)结尾的最长子字符串的长度
        int[] dp = new int[n];
        dp[0] = 1;
        // map存放字符在字符串中的位置
        HashMap<Character,Integer> map = new HashMap<>();
        map.put(ch[0],0);
        int len = 1;
        // list存放最长的子串的结尾index
        ArrayList<Integer> list = new ArrayList<>();
        list.add(0);
        for(int i = 1; i < n; i++){
            if(map.containsKey(ch[i])){
                int idx = map.get(ch[i]);
                dp[i] = Math.min(i - idx,dp[i - 1] + 1);
            }else{
                dp[i] = dp[i - 1] + 1;
            }
            // 不管重复不重复都要存最新的位置
            map.put(ch[i],i);
            if (dp[i] == len){
                list.add(i);
            }else if (dp[i] > len){
                list.clear();
                list.add(i);
                len = dp[i];
            }
        }
        for (int i = 0; i < list.size(); i++){
            int start = list.get(i) - len + 1;
            String ret = s.substring(start,list.get(i) + 1);
            System.out.println(ret);
        }
    }
}