招舟子普通 2023年12月6日下午3:58

class Solution {
public int dismantlingAction(String arr) {
if(arrnull||arr.length()0){
return 0;
}
int[] dp = new int[arr.length()];
dp[0]=1;
int res = 1;
Map<Character,Integer> map = new HashMap<>();
map.put(arr.charAt(0),0);
for(int i=1;i<arr.length();i++){
if(!map.containsKey(arr.charAt(i))){
dp[i] = dp[i-1]+1;
}else{
int k = map.get(arr.charAt(i));
dp[i] =i-k<=dp[i-1]?i-k:dp[i-1]+1;
}
map.put(arr.charAt(i),i);
res = Math.max(res,dp[i]);
}
return res;
}
}
动态规划

0 赞同 0 条回复

九号球普通 2023年12月3日上午10:58

“`java
class Solution {
public int dismantlingAction(String arr) {
if (arr == null || “”.equals(arr)) {
return 0;
}
//dp[j]表示以第j位字母结束的连续不重复招数
//假设arr[i]是于arr[j]重复的元素，
// if i < 0,dp[j] = dp[j-1] + 1; i < 0时，dp[j - 1] < dp[j] 恒成立，所以dp[j - 1] < j - i恒成立 //if dp[j - 1] < j - i,说明重复元素在范围外，dp[j] = dp[j - 1] + 1 //dp[j - 1] = j - i,dp[j] = dp[j - 1] = j - i //dp[j - 1] > j – i,dp[j] = j – i
//最终合并成两个条件
//dp[j – 1] < j - i，dp[j] = dp[j - 1] + 1 //dp[j - 1] >= j – i, dp[j] = j – i;
int length = arr.length();
int pre = 0;
int max = 0;
Map map = new HashMap<>();
for (int j = 0; j < length; j++) { int i = map.getOrDefault(arr.charAt(j), -1); map.put(arr.charAt(j), j); if (pre < j - i) { pre = pre + 1; } else { pre = j - i; } max = Math.max(max, pre); } return max; } }

0 赞同 0 条回复

张开怀普通 2023年7月24日下午3:34

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.empty()) {
            return 0;
        }
        unordered_map<char, int> mp;
        int a = 1;
        mp[s[0]] = 0;
        int res = 1;
        for(int i = 1; i < s.length(); ++i) {
            if(mp.find(s[i]) == mp.end()) {
                ++a;
            } else {
                int k = mp[s[i]];
                a = (i - k <= a) ? (i - k) : (a + 1);
            }
            res = max(res, a);
            mp[s[i]] = i;
        }
        return res;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

Dsjh 普通 2023年7月23日上午12:58

MY

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> v(128,-1);
        int ans=0;
        // i 右边界 j 左边界
        for(int i=0,j=0;i<s.size();i++){
            // 左边界要么不动(即新加入字符没重复)
            // 要么是新加入字符 上次出现位置的下一个位置（重复了）
            // abc b  新加入的是b，那么左边界就是b上次出现位置的下一个，即c的位置
            j = max(j,v[s[i]]+1);
            ans = max(ans,i-j+1);
            v[s[i]] = i;
        }
        return ans;
    }
};

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月23日上午12:56

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        chaMap = {}
        l = 0
        res = 0

        for i in range(len(s)):
            if s[i] in chaMap:
                l = max(l, chaMap[s[i]] + 1)

            res = max(res, i - l + 1)
            chaMap[s[i]] = i

        return res

非模版

0 赞同 0 条回复

BOZ 普通 2023年7月22日上午11:09

【思路】DP，dp[i]代表以s[i]结尾的最长不重复子串长度，可以将额外空间压缩到O(1)
【复杂度】时间O(n^2)，空间O(1)；如果使用map，尽管回溯check时间变短，空间复杂度会上升

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.empty()) return 0;
        int max = 1, prev = 1;

        for (int i = 1; i < s.length(); i++) {
            int k;
            for (k = i - prev; k < i; k++)
                if (s[k] == s[i]) break;
            if (k == i) prev += 1;
            else prev = i - k;
            max = std::max(max, prev);
        }

        return max;
    }
};

0 赞同 0 条回复

花老爷普通 2023年7月21日下午1:29

动态规划
时间：O(n)
空间：O(c)，常数

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int max = 0, start = -1;
        for (int i = 0; i < s.length(); i++) {
            char cur = s.charAt(i);
            if (map.containsKey(cur)) {
                start = Math.max(start, map.get(cur));
            }
            max = Math.max(max, i - start);
            map.put(cur, i);
        }
        return max;
    }
}

0 赞同 0 条回复

局外人普通 2023年7月20日下午6:17

思路：滑动窗口——建立哈希表窗口，每次窗口增大后，检测是否有重复字符，有则消除；然后更新最大长度
时间复杂度：O(n) 空间复杂度：O(n)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLen = 0;
        Map<Character, Integer> window = new HashMap<>();

        int left=0, right=0;
        while(right<s.length()){
            char c = s.charAt(right);
            right++;

            window.put(c, window.getOrDefault(c, 0)+1);

            while(window.get(c)>1){
                char d = s.charAt(left);
                left++;
                window.put(d, window.get(d)-1);
            }
            maxLen = Math.max(maxLen, right-left);
        }

        return maxLen;
    }
}

0 赞同 0 条回复

Ming 普通 2023年7月20日下午5:23

public int lengthOfLongestSubstring(String s) {
        // dp[i]含义：i结尾时不重复字符串的长度
        // 关系式：dp[i] = dp[i-1] + 1,考虑是否在区间内
        // 初始值 dp[0] = 1;
        if(s == null || s.length() <= 0){
             return 0;
        }
        int[] dp = new int[s.length()];
        dp[0] = 1;
        int res = 1;
        Map map = new HashMap<>();
        map.put(s.charAt(0), 0);
        for(int i = 1; i < s.length(); i++) {
            if(!map.containsKey(s.charAt(i))) {
                dp[i] = dp[i-1] + 1;
            } else {
                int k = map.get(s.charAt(i));
                //考虑是否在区间
                dp[i] = i - k <= dp[i-1] ? i - k : dp[i-1] + 1;
            }
            res = Math.max(res, dp[i]);
            map.put(s.charAt(i), i);
        }
        return res;
    }

0 赞同 0 条回复

Yodl. 普通 2023年7月20日下午4:39

//双指针，单变量的dp,时间复杂度O(n)，空间复杂度O(n)
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() == 0) return 0;
        unordered_set<char> h;
        int i,j;
        int ans=0,l=0;
        for(i=0,j=0;j<s.size();j++)
        {
            while(h.find(s[j])!=h.end())
            {
                h.erase(s[i]);
                i++;
            }
            if((j-i+1)>ans)
            {
                ans=(j-i+1);
            }
            h.insert(s[j]);
        }
        return ans;
    }
};

0 赞同 0 条回复

Vow the vow。普通 2023年7月20日上午10:39

同向双指针的特点更明显。都没意识到自己用了单变量的dp

public int lengthOfLongestSubstring(String s) {
        int max = 0;
        char[] arr = s.toCharArray();
        int n = arr.length;
        HashMap<Character,Integer> hashMap = new HashMap<>();
        int l = 0,r = 0;
        while(r < n){
            char ch = arr[r];
            if(hashMap.containsKey(ch)){
                int index = hashMap.get(ch);
                if(index >= l){
                    l = index + 1;
                }
            }
            hashMap.put(ch,r);
            // System.out.println(l + "  " + r);
            max = Math.max(max, r - l +1);
            r++;
        }
        return max;
    }

0 赞同 0 条回复

怀瑾永久会员 2023年7月20日上午8:40

C++实现

“`C++
int lengthOfLongestSubstring(string s) {
unordered_map hashmap;
int left = 0;
int right = 0;
int maxLen = 0;

while (right < s.length()) {
    if (hashmap.find(s[right]) != hashmap.end()) {
        left = std::max(left, hashmap[s[right]] + 1);
    }
    hashmap[s[right]] = right;
    maxLen = std::max(maxLen, right - left + 1);
    ++right;
}

return maxLen;

}

“`

0 赞同 0 条回复

yxy 普通 2023年7月19日下午6:33

双指针复杂度O(n)

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n=s.size();
        if(n==0) return 0;
        unordered_map<char, int> us;
        int res = 0;
        int j=0;
        for(int i=0;i<n;i++)
        {
            char ch = s[i];
            us[ch]++;
            while(us[ch]>1)
            {
                us[s[j]]--;
                j++;
            }
            res = max(res, i-j+1);
        }
        return res;
    }
};

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月19日下午6:13

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0){
            return 0;
        }
        int dp = 1;
        int max = 1;
        List<Character> curChars = new ArrayList();
        curChars.add(s.charAt(0));

        for(int i = 1;i < s.length();i++){
            char curChar = s.charAt(i);
            if(curChars.contains(curChar)){

                //删除重复元素，及其往前的元素
                int index = curChars.indexOf(curChar);
                for(int j = 0;j <= index;j++){
                    curChars.remove(0);
                }

                dp = curChars.size() + 1; //出现重复
                curChars.add(curChar);
            }else{
                dp = dp + 1;
                curChars.add(curChar);
                max = Math.max(dp,max);
            }
        }

        return max;
    }
}

0 赞同 0 条回复

【动态规划专题】剑指 Offer 48. 最长不含重复字符的子字符串

共以下 14 个回答

MY

# 回答此问题取消回复

【动态规划专题】剑指 Offer 48. 最长不含重复字符的子字符串

共以下 14 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复