[leetcode题目解答]--(3)无重复字符的最长子串

Author：赵志乾
Date：2019-03-27
Declaration：All Right Reserved！！！

 

1、题目描述

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。(只包含ASCII码)

2、示例

示例 1:
    输入: "abcabcbb"
    输出: 3 
    解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
    输入: "bbbbb"
    输出: 1
    解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
    输入: "pwwkew"
    输出: 3
    解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
         请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

3、解答

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 定义结果
        int ret = 0;
        // 入参判定
        if(s==null||s.length()==0){
            return ret;
        }
        // 定义字符与下标映射
        int[] index = new int[128];
        // 遍历处理
        for (int indexPre = 0, indexCur = 0; indexCur < s.length(); indexCur++) {
            // 出现重复字符时，更新左边界
            indexPre = Math.max(index[s.charAt(indexCur)], indexPre);
            // 更新最长子串长度
            ret = Math.max(ret, indexCur-indexPre + 1);
            // 更新字符下标
            index[s.charAt(indexCur)] = indexCur + 1;
        }
        // 返回结果
        return ret;
    }
}

4、复杂度分析

假设字符集长度为m，字符串长度为n，则时间复杂度为O(n),空间复杂度为O(min(m,n))。

 

题目出处：leetcode网站