无重复字符的最长子串算法题解C/C++/JAVA/Python

题目:

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入:"abcabcbb",输出:3 

解释:因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入:"bbbbb",输出: 1

解释:因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入:"pwwkew",输出: 3

解释:因为无重复字符的最长子串是 "wke",所以其长度为 3。

请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

C解法:

int max(int a, int b)
{
    return a > b ? a : b;
}
int lengthOfLongestSubstring(char *s)
{
    int n = strlen(s);
    int l[256] = {0};
    int r = 0;
    for (int i = 0, j = 0; j < n; j++)
    {
        i = max(l[s[j]], i);
        r = max(j - i + 1, r);
        l[s[j]] = j + 1;
    }
    return r;
}

C++解法:

class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        int n = s.length(), len = 0;
        unordered_map<int, int> map;
        for (int i = 0, j = 0; j < n; j++)
        {
            if (map.find(s[j]) != map.end())
            {
                i = max(map[s[j]], i);
            }
            len = max(len, j - i + 1);
            map[s[j]] = j + 1;
        }
        return len;
    }
};

JAVA解法:

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

Python3解法:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n, i = len(s), 0
        result = 0
        map = {}
        for j in range(n):
            if s[j] in map:
                i = max(map[s[j]] , i)
            result = max(result, j - i + 1)
            map[s[j]] = j + 1
        return result
共 0 条评论