首页>itarticle>longest substring without repeating characters
longest substring without repeating characters
admin11月 14, 20200
Given a string, find the length of the longest substring without repeating characters.
Example 1:
1 2 3
Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.
Example 2:
1 2 3
Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.
Example 3:
1 2 3 4
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.
题目大意:给定一个字符串,求出最长连续子串的长度。
int[26] for Letters ‘a’ - ‘z’ or ‘A’ - ‘Z’
int[128] for ASCII
int[256] for Extended ASCII
神奇的解法。时间复杂度 O(n)
1 2 3 4 5 6 7 8 9 10 11 12
publicclass{ publicintlengthOfLongestSubstring(String s){ int n = s.length(), ans = 0; int[] index = newint[128]; 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; } }
近期评论