3. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb"
, the answer is "abc"
, which the length is 3.
Given "bbbbb"
, the answer is "b"
, with the length of 1.
Given "pwwkew"
, the answer is "wke"
, with the length of 3. Note that the answer must be a substring, "pwke"
is a subsequence and not a substring.
Solution
(1) Java
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int rst = 1;
int start = 0;
char[] arr = s.toCharArray();
Map<Character, Integer> map = new HashMap<>();
map.put(arr[0],0);
for (int i = 1; i < s.length(); i++) {
char c = arr[i];
if (map.containsKey(c) && map.get(c) >= start) {
start = map.get(c)+1;
}
map.put(c, i);
rst = Math.max(rst, i-start+1);
}
return rst;
}
(2) Python
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
if not s:
return 0
rst = 1
cache = {s[0]:0}
start = 0
for i in range(1, len(s)):
c = s[i]
if c in cache and cache[c] >= start:
start = cache[c]+1
cache[c]=i
rst = max(rst, i-start+1)
return rst
(3) Scala
object Solution {
def lengthOfLongestSubstring(s: String): Int = {
var start:Int = 0
var idxMap:Map[Char, Int] = Map()
var rst:Int = 0
for (i <- 0 until s.length()) {
var c = s.charAt(i)
if (idxMap.contains(c) && idxMap(c) >= start) {
rst = rst.max(i-start)
start = idxMap(c)+1
}
idxMap += (c -> i)
}
rst = rst.max(s.length()-start)
return rst
}
}