Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
http://leetcode.com/2011/05/longest-substring-without-repeating-characters.html
Read full article from LeetCode – Longest Substring Without Repeating Characters (Java)
http://leetcode.com/2011/05/longest-substring-without-repeating-characters.html
int lengthOfLongestSubstring(string s) {
int n = s.length();
int i = 0, j = 0;
int maxLen = 0;
bool exist[256] = { false };
while (j < n) {
if (exist[s[j]]) {
maxLen = max(maxLen, j-i);
while (s[i] != s[j]) {
exist[s[i]] = false;
i++;
}
i++;
j++;
} else {
exist[s[j]] = true;
j++;
}
}
maxLen = max(maxLen, n-i);
return maxLen;
}
public static int lengthOfLongestSubstring3(String s) {
int max = 0;
HashSet<Character> set = new HashSet<Character>();
int candidateStartIndex = 0;
for (int iter = 0; iter < s.length(); ++iter) {
char c = s.charAt(iter);
if (set.contains(c)) {
max = Math.max(max, iter - candidateStartIndex);
while (s.charAt(candidateStartIndex) != s.charAt(iter)) {
set.remove(s.charAt(candidateStartIndex));
candidateStartIndex++;
}
candidateStartIndex++;
} else {
set.add(c);
}
}
max = Math.max(max, s.length() - candidateStartIndex);
return max;
}
LeetCode – Longest Substring Without Repeating Characters (Java)public static int lengthOfLongestSubstring(String s) { char[] arr = s.toCharArray(); int pre = 0; HashMap<Character, Integer> map = new HashMap<Character, Integer>(); for (int i = 0; i < arr.length; i++) { if (!map.containsKey(arr[i])) { map.put(arr[i], i); } else { pre = pre > map.size() ? pre : map.size(); i = map.get(arr[i]); map.clear(); } } return Math.max(pre, map.size()); } |
No comments:
Post a Comment