String-mainipulation8

发表于 分类于 ，

题目描述[原题描述][https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/]

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

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

输入: “pwwkew”
输出: 3

解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

算法分析

​ 用哈希表(unordered_map)存字符串，出现重复的字符后，把之前的字符弹出后再继续读，每次取最大的长度保存到变量中，直到字符串到结束

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> hash;
        int res=0;
        for(int i=0,j=0;i<s.length();i++){
            if(++hash[s[i]]>1){
                while(i>j){
                    hash[s[j]]--;
                    j++;
                    if(hash[s[i]]==1)break;
                }
            }
            res = max(res,i-j+1);
        }
        return res;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character,Integer> hp  = new HashMap<Character,Integer>();
        int res = 0;
        for(int i=0,j=0;i<s.length();i++){
            if(hp.containsKey(s.charAt(i))){
               j = Math.max(hp.get(s.charAt(i)),j);
            }
            res = Math.max(res,i-j+1);
            hp.put(s.charAt(i),i+1);
        }
        return res;
    }
}