当前位置: 首页 > >

3. Longest Substring Without Repeating Characters

发布时间:

Discription:




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.







Explanation:
set two pointers i and j, i represents the head of substring, j represents the tail of substring.
use a map to store the last index the letters appeared.
first i=j=0;
ans = 0
iterate j from 0 to s.length-1
if s[j] is in map then set i=max(i, map[s[j]]+1).
set map[s[j]]=j
ans=max(j-i+1, ans)




Implement code:
C++:
class Solution {
public:
? ? int lengthOfLongestSubstring(string s) {
? ? ? ? int l=s.length();
? ? ? ? int i=0,j=0;
? ? ? ??
? ? ? ? int ans=0;
? ? ? ? unordered_map m;
? ? ? ??
? ? ? ? for(;j? ? ? ? {
? ? ? ? ? ? if(m.count(s[j]))i=max(i, m[s[j]]+1);
? ? ? ? ? ? ans = max(ans, j-i+1);
? ? ? ? ? ? m[s[j]]=j;
? ? ? ? }
? ? ? ??
? ? ? ? return ans;
? ? }
};





Java:
import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;
import java.io.BufferedInputStream;


public class Solution
{
public int lengthOfLongestSubstring(String s) {
? ? ? ? int ans=0;
int i=0, j=0;


Map m = new HashMap();
for(;j{
char c = s.charAt(j);
if(m.containsKey(c))
{
i = Math.max(i, (int)m.get(c) + 1);
}
m.put(c, j);
ans = Math.max(ans, j-i+1);
}


return ans;
? ? }

/*
public static void main(String[] args)
{
Scanner sc = new Scanner(new BufferedInputStream(System.in));

while(sc.hasNext())
{
String s = sc.next();


System.out.println(new Solution().lengthOfLongestSubstring(s));
}
}


*/
}






友情链接: