请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。
数据范围:
"abcabcbb"
3
因为无重复字符的最长子串是"abc",所以其长度为 3。
"bbbbb"
1
因为无重复字符的最长子串是"b",所以其长度为 1。
"pwwkew"
3
因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是子串的长度,"pwke" 是一个子序列,不是子串。
public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param s string字符串 * @return int整型 */ public int lengthOfLongestSubstring (String s) { // write code here if (s.length() == 0 && s.equals(" ")) return 0; int currentLen = 0; int maxLen = 0; char[] chars = s.toCharArray(); HashMap<Character, Integer> map = new HashMap<>(); for (int i = 0; i < chars.length; i++) { if (map.containsKey(chars[i])){ int d=i-map.get(chars[i]); if (d>currentLen) currentLen++; else currentLen=d; }else { currentLen++; } if (currentLen>maxLen) maxLen=currentLen; map.put(chars[i],i); } return maxLen; } }
import java.util.*; public class Solution { public int lengthOfLongestSubstring (String s) { // 定义最大长度 int max=0; // 定义start指针,初始值为-1是考虑到length=1的输入 int start=-1; // 定义hashmap,key为字符,value为最后一次出现的位置 HashMap<Character,Integer> map = new HashMap<>(); // 遍历字符串 for(int i=0;i<s.length();i++){ char cur = s.charAt(i); // 只有当重复元素出现在start后方时,才更新start(避免start向前更新) if(map.containsKey(cur) && map.get(cur) > start){ start = map.get(cur); } // 实时更新map map.put(cur,i); // 更新最大长度 max = Math.max(max, i-start); } // 返回最大长度 return max; } }
from queue import deque class Solution: def lengthOfLongestSubstring(self , s: str) -> int: if not s: return 0 q = deque() # 初始无重复最长子串长度 max_substr = 0 for i in s: if i not in q: q.append(i) # 更新max_substr if len(q) > max_substr: max_substr = len(q) else: # 从队列中弹出重复元素i以及i之前的所有元素 while i in q: q.popleft() # 弹出之后将i入队 q.append(i) return max_substr
public int lengthOfLongestSubstring(String s) { int b = 0; int key = 0; List<Character> res = new ArrayList<>(); while (b != s.length()) { if (res.contains(s.charAt(b))){ List<Character> code = new ArrayList<>(); for (Character re : res) { if (re == s.charAt(b)) { code.add(re); break; } else code.add(re); } res.removeAll(code); res.add(s.charAt(b)); b++; }else { res.add(s.charAt(b)); b++; } key = Math.max(key,res.size()); } return key; }
public int lengthOfLongestSubstring(String s) { // write code here // 典型的额双指针问题 int len = s.length(); if(len <= 1) return s.length(); int maxLen = 0; ArrayList<Character> charList = new ArrayList<>(); for (int i = 0; i < len; i++) { for (int j = i; j < len; j++) { char c = s.charAt(j); if(!charList.contains(c)) charList.add(c); else { maxLen = Math.max(maxLen, charList.size()); charList.clear(); break; } } } return maxLen; }
public int lengthOfLongestSubstring(String s) { // write code here int len = 0; int[] hash = new int[256]; int j = 0; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); hash[c]++; // 初始化时,每个元素对应 ASCII 的数字的值为 1 while (hash[c] > 1) { // 发现有重复的字符串 // 寻找重复元素的下一个下标,退出就是为 j hash[s.charAt(j)] --; j++; } // 当前的最大值 len = Math.max(i - j + 1, len); // 继续往下寻找... } return len; }
package main /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param s string字符串 * @return int整型 */ func lengthOfLongestSubstring(s string) int { // write code here var char2Index = make(map[int32]int, len(s)) var maxSub = 0 var currentSubLen = 0 var getMax = func(a, b int) int { if a > b { return a } return b } var left int for index, char := range s { if charIdx, exist := char2Index[char]; exist { if charIdx < left { currentSubLen += 1 } else { maxSub = getMax(currentSubLen, maxSub) currentSubLen = index - charIdx left = charIdx + 1 } } else { currentSubLen += 1 } char2Index[char] = index } maxSub = getMax(currentSubLen, maxSub) return maxSub }
function lengthOfLongestSubstring(s) { // write code here if (!s) return 0; let dic = new Map(); let dp = [1]; let m = 1; dic.set(s[0], 0); for (i = 1; i < s.length; i++) { let j = dic.get(s[i]); dp[i] = j === undefined || dp[i - 1] < i - j ? dp[i - 1] + 1 : i - j; dic.set(s[i], i); m = Math.max(m, dp[i]); } return m; }
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param s string字符串 * @return int整型 */ #include <string.h> #define max(x,y)((x)>(y)?(x):(y)) int lengthOfLongestSubstring(char* s ) { // write code here int len = strlen(s); //appear数组类似于哈希表 appear[s[i]]存放每个字符出现过的次数 //s[i]是字符 如abcab s[0]==s[3]=='a' //不难发现 appear[s[0]]==appear[s[3]]==appear['a'] int appear[10000] = {0}; //ans保存最大长度 int ans = 0; //i和j是不含重复字符的子字符串的首尾指针 for (int i=0, j=0; j<len; j++) { //尾指针j开始扫描 字符出现就次数+1 appear[s[j]]++; //存在重复出现的字符 //如abcab appear[s[0]]==appear[s[3]]==appear[a] while (i<j && appear[s[j]]>1) { //重复出现的字符 出现次数-1 appear[s[i]]--; //首指针i向后移动一位 i++; } //ans取ans和每次子串长度的最大值 ans = max(ans, j-i+1); } return ans; }
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param s string字符串 * @return int整型 */ int lengthOfLongestSubstring(string s) { // 时间复杂度O(N),空间复杂度O(N) unordered_set<char> hash; int left = 0, right = 0, res = 0; while (right < s.size()) { while (hash.find(s[right]) != hash.end()) { hash.erase(s[left]); ++left; } hash.insert(s[right]); ++right; res = max(res, right - left); } return res; } };
public int lengthOfLongestSubstring(String s) { // 记录字符上一次出现的位置 int[] last = new int[128]; for (int i = 0; i < 128; i++) last[i] = -1; int start = 0; int res = 0; for (int i = 0; i < s.length(); i++) { int index = s.charAt(i); // 控制窗口开始位置 start = Math.max(start, last[index] + 1); // 判断哪个窗口更长 res = Math.max(res, i - start + 1); // 记录出现位置 last[index] = i; } return res; }
public int lengthOfLongestSubstring (String s) { // write code here HashMap<Character, Integer> map = new HashMap<>(); int res = 0; int l = 0; for (int i = 0; i < s.length(); i++) { if (map.containsKey(s.charAt(i))) { map.put(s.charAt(i), map.get(s.charAt(i)) + 1); } else { map.put(s.charAt(i), 1); } //重复了就一直移动左边界 直到不重复 while (map.get(s.charAt(i)) > 1) { map.put(s.charAt(l), map.get(s.charAt(l)) - 1); l++; } res = Math.max(res, i - l + 1); } return res; } }
public int lengthOfLongestSubstring (String s) { int max=0; int start=0; char[] chars = s.toCharArray(); Set<Character> set = new HashSet<>(); for (int end = 0; end < chars.length; end++) { while (set.contains(chars[end])){ set.remove(chars[start]); start++; } set.add(chars[end]); max=Math.max(max,end-start+1); } return max; }
public int lengthOfLongestSubstring (String s) { // write code here int max = 0; boolean[] sign = new boolean[256]; int left = 0, right = 0; while (right < s.length()) { char ch = s.charAt(right); if (sign[ch]) { while (s.charAt(left) != ch) { sign[s.charAt(left ++)] = false; } sign[s.charAt(left ++)] = false; } sign[ch] = true; right ++; max = Math.max(max, right - left); } return max; }
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: maxlen = 0 char_map = {} init = -1 for i in range(0, len(s)): if s[i] in char_map: if s[i] in char_map: index = max(init, char_map[s[i]]) maxlen = max(maxlen, i - index) init = max(init, char_map[s[i]]) char_map[s[i]] = i else: maxlen = max(maxlen, i - init) char_map[s[i]] = i return maxlen
public int lengthOfLongestSubstring (String s) { // write code here HashMap<Character, Integer> mp = new HashMap<>(); int res = 0; if(s.length() <= 1){ return s.length(); } int left = 0, right = 0; while(right < s.length()){ if(mp.containsKey(s.charAt(right))){ mp.put(s.charAt(right), mp.get(s.charAt(right)) + 1); } else { mp.put(s.charAt(right), 1); } if(mp.get(s.charAt(right)) > 1){ // 因为每次subring提取出来的字符串索引值都是从0开始, // 所以需要加上左边界left,才能表示s.charAT(right)字符在s中的索引位置 int index = s.substring(left, right).indexOf(s.charAt(right)) + left; mp.put(s.charAt(right), mp.get(s.charAt(right))-1); // 保证字符left,right区间的字符只出现一次。如果不做这一步,假设abcac,此时a重复了,在区间[0,4]之间,a出现两次,移动left到1时,a在[1,4]之间只出现一次,如果不-1,则还是两次,就会判定错误。 res = Math.max(res, right - left); left = index + 1; } right++; } // 会出现一种情况,right一直到结束,都没有重复,此时就无法进入if条件判断长度 // 需要在循环结束时,判断最后一个是否重复? 重复,说明已经进入循环内的if判断过 // 不重复,说明还需要再进行判断一次,判断res 与 当前right - left 长度 return mp.get(s.charAt(right-1)) == 1 ? res = Math.max(res, right - left) : res;