|
| 1 | +/* |
| 2 | + Author: King, wangjingui@outlook.com |
| 3 | + Date: Dec 12, 2014 |
| 4 | + Problem: Longest Substring Without Repeating Characters |
| 5 | + Difficulty: Medium |
| 6 | + Source: https://oj.leetcode.com/problems/longest-substring-without-repeating-characters/ |
| 7 | + Notes: |
| 8 | + Given a string, find the length of the longest substring without repeating characters. |
| 9 | + For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. |
| 10 | + For "bbbbb" the longest substring is "b", with the length of 1. |
| 11 | +
|
| 12 | + Solution: 1. Pay attention when moving the 'start' pointer forward. |
| 13 | + 2. More space, but maybe faster. |
| 14 | + */ |
| 15 | +publicclassSolution { |
| 16 | +publicintlengthOfLongestSubstring_1(Strings) { |
| 17 | +boolean[]hash =newboolean[256]; |
| 18 | +Arrays.fill(hash,false); |
| 19 | +intn =s.length(); |
| 20 | +if (n <=1)returnn; |
| 21 | +intstart =0,end =0,res =0; |
| 22 | +while (end <n &&start +res <n) { |
| 23 | +if (hash[s.charAt(end)] ==false) { |
| 24 | +hash[s.charAt(end++)] =true; |
| 25 | + }else { |
| 26 | +hash[s.charAt(start++)] =false; |
| 27 | + } |
| 28 | +res =Math.max(res,end -start); |
| 29 | + } |
| 30 | +returnres; |
| 31 | + } |
| 32 | +publicintlengthOfLongestSubstring_2(Strings) { |
| 33 | +int[]hash =newint[256]; |
| 34 | +Arrays.fill(hash, -1); |
| 35 | +intn =s.length(); |
| 36 | +if (n <=1)returnn; |
| 37 | +hash[s.charAt(0)] =0; |
| 38 | +intstart =0,res =1,cur =0; |
| 39 | +while (++cur <n) { |
| 40 | +if (hash[s.charAt(cur)] >=start) { |
| 41 | +start =hash[s.charAt(cur)] +1; |
| 42 | + } |
| 43 | +res =Math.max(res,cur -start +1); |
| 44 | +hash[s.charAt(cur)] =cur; |
| 45 | + } |
| 46 | +returnres; |
| 47 | + } |
| 48 | +} |
