Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew" Output: 3 Explanation: 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: Brute force
class Solution {
public int lengthOfLongestSubstring(String s) {
int ln = s.length();
int res = 0;
for(int i = 0; i < ln; i++){
for(int j = i+1; j <=ln; j++){
if(isUnique(s, i, j))res = Math.max(res, j-i);
}
}
return res;
}
public boolean isUnique(String st, int start, int end){
ArrayList<Character> list = new ArrayList<Character>();
for(int i = start; i < end; i++){
Character ch = st.charAt(i);
if(list.contains(ch)) return false;
list.add(ch);
}
return true;
}
}
主程序重用两层for loop保证每个组合可以被检查，用什么检查呢？用isUnique method。然后submit，Time limit Exceeded。。
SOlution2：
public class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(), ans = 0; int[] index = new int[128]; // current index of character // try to extend the range [i, j] for (int j = 0, i = 0; j < n; j++) { i = Math.max(index[s.charAt(j)], i); ans = Math.max(ans, j - i + 1); index[s.charAt(j)] = j + 1; } return ans; } }
3. Longest Substring Without Repeating Characters
原文：https://www.cnblogs.com/wentiliangkaihua/p/10204173.html