3. Longest Substring Without Repeating Characters
难度: Medium
刷题内容
原题连接
- https://leetcode.com/problems/longest-substring-without-repeating-characters
内容描述
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.
解题方案
思路 1 **- 时间复杂度: O(N)*- 空间复杂度: O(1)***
class Solution {
public int lengthOfLongestSubstring(String s) {
int stIdx = 0, maxLen = 0;
int arr[] = new int[128];
for(int i=0;i<s.length();i++){
stIdx = Math.max(arr[s.charAt(i)],stIdx);
maxLen = Math.max(maxLen, i-stIdx+1);
arr[s.charAt(i)] = i+1;
}
return maxLen;
}
}
