Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Latest commit

 

History

History
History
48 lines (47 loc) · 1.66 KB
/

LongestSubstringWithoutRepeatingCharacters.java

File metadata and controls

48 lines (47 loc) · 1.66 KB
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/*
Author: Andy, nkuwjg@gmail.com
Date: Dec 12, 2014
Problem: Longest Substring Without Repeating Characters
Difficulty: Medium
Source: https://oj.leetcode.com/problems/longest-substring-without-repeating-characters/
Notes:
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.
Solution: 1. Pay attention when moving the 'start' pointer forward.
2. More space, but maybe faster.
*/
public class Solution {
public int lengthOfLongestSubstring_1(String s) {
boolean[] hash = new boolean[256];
Arrays.fill(hash,false);
int n = s.length();
if (n <= 1) return n;
int start = 0, end = 0, res = 0;
while (end < n && start + res < n) {
if (hash[s.charAt(end)] == false) {
hash[s.charAt(end++)] = true;
} else {
hash[s.charAt(start++)] = false;
}
res = Math.max(res, end - start);
}
return res;
}
public int lengthOfLongestSubstring_2(String s) {
int[] hash = new int[256];
Arrays.fill(hash, -1);
int n = s.length();
if (n <= 1) return n;
hash[s.charAt(0)] = 0;
int start = 0, res = 1, cur = 0;
while (++cur < n) {
if (hash[s.charAt(cur)] >= start) {
start = hash[s.charAt(cur)] + 1;
}
res = Math.max(res, cur - start + 1);
hash[s.charAt(cur)] = cur;
}
return res;
}
}
Morty Proxy This is a proxified and sanitized view of the page, visit original site.